- 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:

[http://stackoverflow.com/questions/3255/big-o-how-do-you-calculateapproximate-it]

[http://stackoverflow.com/questions/107165/big-o-for-eight-year-olds]

[http://stackoverflow.com/questions/133008/what-is-big-o-notation-do-you-use-it]

- 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

[http://www.softpanorama.org/Algorithms/sorting.shtml]

- Counting sort animation

[http://www.cs.unc.edu/~stotts/145/homes/animate/project/SORTING/CountingSort/Control.htm]