Algorithms Notes
• O(1) means whatever you do, you need 1 step.

O(N) means whatever you do, you need N steps, like iterating over a list with N elements
O(log N) means you need log N steps, like a binary tree search over N elements.

• Upper Bound: An asymptotic bound, as function of the size of the input, on the worst (slowest, most amount of space used, etc.) an algorithm will do to solve a problem. That is, no input will cause the algorithm to use more resources than the bound.
• Lower Bound: An asymptotic bound, as function of the size of the input, on the best (fastest, least amount of space used, etc.) an algorithm can possibly achieve to solve a problem. That is, no algorithm can use fewer resources than the bound.
• Big O Notation Resources:
• Recurrence Relations to Remember:

Recurrence Algorithm Big-Oh Solution
--- -— ---
T(n) = T(n/2) + O(1) Binary Search O(log n)
T(n) = T(n-1) + O(1) Sequential Search O(n)
T(n) = 2 T(n/2) + O(1) tree traversal O(n)
T(n) = T(n-1) + O(n) Selection Sort (other n2 sorts) O(n^2)
T(n) = 2 T(n/2) + O(n) Mergesort (average case Quicksort) O(n log n)

• Sorting algorithms view with time comparison on some machines //good explanation
• Counting sort animation
page revision: 5, last edited: 04 Dec 2008 23:44