Assess the complexity of an algorithm from worse cases of input size:
O(1): constant running time (or ‘Constant Complexity’); all mathematical operations are O(1);
def inc(x): return x+1
O(log n): logarithmic running time. Such as bisection search. For loops are generally this. costs grow slowly
O(n): linear running time: Such as searching a list for an element. Recursion examples so far in class are linear.
O(n log n): log-linear running time: a lot of common algorithms, such as a merge sort. Still really valuable.
O(n^c) polynominal running time (c is a constant): nested loops a good example. Quadratic complexity.
O(c^n) exponential running time (c is constant, raised to a power based on the size of the list.) – often recursive functions such as Towers of Hanoi. Generate a list of all possible subsets out of a list. Many important problems are exponential, better to find approximate solutions more quickly.