Complexity Classes

Notes from Week 5 of the MIT Introduction to Computer Science 6.00.1 MOOC. Extensive notes in this .pdf from the class. Further notes related to python here:

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.

Leave a Reply