Complexity

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)) means c*g(n) is an upper bound on f(n).
f(n) = Ω(g(n)) means c*g(n) is a lower bound on f(n).
f(n) = Θ(g(n)) means c1*g(n) is an upper bound on f(n) and c2*g(n) is a lower bound on f(n).
With Big Oh we discard multiplication of constants: n^2 and 1000*n^2 are treated identically.
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
O(f(n)) + O(g(n)) => O(max(f(n), g(n))) => n^3 + n^2 + n + 1 = O(n^3)
O(f(n)) ∗ O(g(n)) => O(f(n) ∗ g(n))

Recursion Complexity Analysis

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)

All pairs: O(n^2)
All triples: O(n^3)
Number of all permutations: n!
n over k: number of combinations for choosing k items from a set of n
- (n over k) = n!/(k!*(n-k)!)
Number of subsets from a set of n: 2^n
- Subset = any unique set of k elements from n, including the empty set).
- For example: set={1,2,3}, subsets={},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} (ordering in a set doesn't matter).