design analysis mid

Space Efficiency or Complexity

The amount of computer space or memory required by an algorithm to complete its execution and produce the result

Constant Space Complexity

Space complexity that remains the same regardless of input size

Linear Space Complexity

Space complexity that increases proportionally with input size

Instruction space

Amount of memory used to store a compiled version of instructions

Data space

Amount of memory used to store all variables and constants

Run-time Stack Space

Amount of memory used to store information of partially executed functions during function calls

Time Efficiency or Complexity

Amount of computer time required for an algorithm to execute

T(n)

Amount of computer time required by each operation to execute

Cop

Amount of computer time required for a single operation in each line

C(n)

Amount of computer time required by each operation for all its repetitions

Constant Time Complexity

Time complexity where execution time does not change with input size

Linear Time Complexity

Time complexity where execution time increases proportionally with input size

Asymptotic Notations

Mathematical languages used to describe algorithm growth rate as input size increases

Big-O Notation

Describes the asymptotic upper bound or worst-case growth rate of an algorithm. Also known as Landau’s symbol

Big-Omega Notation

Describes the asymptotic lower bound or best-case growth rate of an algorithm

Big-Theta Notation

Describes the asymptotic tight bound of an algorithm’s growth rate

Recursive

A function or method that solves a problem by calling itself on smaller instances

Base case

Simplest instance of a recursive problem that cannot be decomposed further

Recursive step

Part of recursion that breaks a problem into smaller instances and recombines results

Recurrence Relation

Equation that defines a function in terms of itself with smaller arguments

Substitution Method

Method used to solve recurrences by guessing and verifying the solution using induction

Recursion Tree Method

suitable for generating guesses for the substitution method and promoting intuition

Master Method

Technique used to determine time complexity of divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n)

Steps to solve recurrence relations using recursion tree method

draw a recursion tree. Determine the cost of each level, total number of levels, number of nodes in the last last level, and cost of the last level. Add the cost of all the levels of the recursion tree and simplify the expression so obtained in terms of asymptotic notation

When is master theorem not applicable?

a is not constant, the difference f(n) and n logba is not polynomial m, a < 1 cannot have less than one sub problem, f(n) is not positive

Steps of substitution method

guess the form of the solution, verify by mathematical induction, solve constants to show that the solution works

The proof consists two steps

• The basis (base case or boundary) or induction goal. (T(0)=time to solve problem of size 0)

• The induction hypothesis. (T(n) = time to solve the problem of size n)

Computer’s speed

An algorithm may run faster in one machine but not to another machine because it depends on the computers speed. Limited computer memory affects the efficiency of the algorithm

Quality of the program implementing the algorithm

Running complex programs is difficult as compared to running simple programs, usually it depends on the input size like sorting algorithm that does better on small lists but slower on longer lists.

Compiler used in generating the machine code

The use of compiler generating the machine code affects the efficiency of the algorithm because once in the process of compilation, the compiler effectively controls the final configuration of hardware and how it operates.

Algorithm’s growth rate

These are set of languages that allow us to analyze an algorithm’s running time to asymptotic analysis by identifying its behavior as the input size for the algorithm increases