Factors:
- Hardware(processor, memory), Software(OS, compiler, language), and Human(programmer habitat) factors
- single/multiple processor, generation of processor, R/W speed to memory. 32/64-bit. Input size/kind
- for (int i = 0 to n-1) executed 2(n+1) units. (1 comparison + 1 incrementation)*(n + 1false_check)
Complexity Basics
Big Oh – measuring run time by counting the number of steps an algorithm takes (translating to actual time is trivial).
f(n) = O(g(n))meansc*g(n)is an upper bound onf(n)f(n) = Ω(g(n))meansc*g(n)is a lower bound onf(n)f(n) = Θ(g(n))meansc1*g(n)is an upper bound onf(n)andc2*g(n)is a lower bound onf(n)Growth rates: 1 < log(n) < n < n*log(n) < n^2 < n^3 < 2^n < n!
- Constant functions
- Logarithmic: binary search, arises in any process where things are repeatedly halved or doubled
- Linear: traversing every item in an array
- Super-linear: quicksort, mergesort
- Quadratic: going thru all pairs of elements, insertion sort, selection sort
- Cubic: enumerating all triples of items
- Exponential: enumerating all subsets of n items
- Factorial: generating all permutations or orderings of n items
Recursion Complexity Analysis
- Let
T(n)be the recursive function. - Below are examples of inner calls of
T(n), their complexity, and example algorithm that uses them:T(n) = T(n/2) + O(1) --> O(log(n)), binary searchT(n) = T(n-1) + O(1),O(n),sequential searchT(n) = 2*T(n/2) + O(1),O(n)tree traversalT(n) = 2*T(n/2) + O(n,O(n*log(n)), merge sort, quick sortT(n) = T(n-1) + O(n),O(n^2), selection sort
Combinatorics
- All pairs:
O(n^2) - All triples:
O(n^3) - Number of all permutation
n! noverk: number of combinations for choosing items from a set ofn: (n over k) = n!/(k!*(n-k)!)- Number of subsets from a set of
n:2^n
Handy formulas
x + x/2 + x/4 +.... = 2x
Geometric progression: a(n) = a(1)*q^(n-1); S(n) = a(1)*(q^n-1)/(q - 1). If it converges: S(inf) = a(1)/(1 - q)
Exercise:
for(i = 0; i < n; i += 2) --> n/2
for(i = 1; i < n; i *= 2) --> log(n)
for(i = n; i > -1; i /= 2) --> never terminate