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:

[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]

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License