Algorithm concepts Flashcards
Uniform cost model
All machine operations have a constant cost, whatever the values
Time complexity
T(N) = aN + b
Asymptotic notation
aN + b = O(N) T(N) = O(N) highest order term determines the bound
Definition “Big O” (Upper Bound)
A function f(N) has an asymptotic upper bound given by the function g(N), written f(N) = O(g(N)), if and only if there are positive real numbers c and n0 such that 0 ≤ f(N) ≤ c g(N) for all N ≥ n0
Definition “Big Omega” (Lower Bound)
A function f(N) has an asymptotic lower bound given by the function g(N), written f(N) = Ω(g(N)), if and only if there are positive real numbers c and n0 such that 0 ≤ c g(N) ≤ f(N) for all N ≥ n0
Definition “Big Theta” (Tight Bound)
A function f(N) has an asymptotic tight bound given by the function g(N), written f(N) = Θ(g(N)), if and only if there are positive real numbers c1, c2, and n0 such that 0 ≤ c1 g(N) ≤ f(N) ≤ c2 g(N) for all N ≥ n0
Space complexity
The space complexity of an algorithm is the total amount of memory used, including that used by input parameters, as a function of the size of the input
Auxiliary Space
The auxiliary space is the amount of extra memory required, not including input parameters, as a function of the size of the input.
Polynomial
p(N) = a0 + a1N + a2N^2 + … + adN^d in which ad ≠ 0 asymptotically positive iff ad > 0
Exponential
include a term of the form a^N
Divide and Conquer

Recursion Tree

Master Method

Master Method pt 2

Master Method pt 3 (extra check)
Regularity condition

Master method excluded cases
The master method does not apply to these recurrences
T(N) = NT(N/2) + N T(N) = 0.5T(N/2) + 4N T(N) = 4T(N/8) − N2
T (N ) = 2T (N /2) + N / log N
The (mostly straightfoward) reasons are
the number of subproblems in the first two
negative divide and combine time (third example)
negative value of k (fourth example)
Heap

Binary search tree add code

Hash function
common to implement hash function in two steps
either stage can cause collisions

Adjacency lists

Code for Kruskal’s

Prim’s code

Bellman-Ford

Relax

Bellman-Ford to detect negative weight cycle

Bellman-Ford

Dijkstra

Dijkstra’s correctness

Dijkstra’s correctness pt 2
