Big O Notation

Task: Watch how each complexity class grows as the input gets bigger

a[i]                                   // O(1)binarySearch(a, target)                // O(log n)for (int v : a) sum += v               // O(n)Arrays.sort(a)                         // O(n log n)for (int x : a) for (int y : a) cmp++  // O(n^2)allSubsets(a)                          // O(2^n)allPermutations(a)                     // O(n!)

What you are watching

Seven complexity classes drawn one at a time on the same axes, from best to worst. O(1) stays flat, O(log n) almost flat, and O(n) runs to the far corner as the diagonal. O(n log n), O(n squared), O(2 to the n) and O(n factorial) each leave the top of the frame, in that order, and the last of them is gone before the input reaches five - which is why a factorial algorithm has an input size it can never finish.