Prove that n^k, k >=0,  is strictly faster than c^n (where c > 1).
n^k = o (c^n).

Remember induction.  If it's true for k=0, and you can demonstrate if it's true for k=m, it must also be true for k=m+1, then you know it's true if k is any nonnegative integer.

So, how about k=0?

lim n->inf  n^0 / c^n?   lim n->inf 1 / c^n.   This is 1/inf which is zero.


So, this means that any algorithm that runs in n^k time is faster than any algorithm running in c^n time, (k>=0, c > 1).  So, an algorithm that runs in n^1000000 is faster than an algorithm running in (1.00001)^n.

If an algorithm runs in O(n^k) time (for some k), we call it a polynomial-time algorithm.  They are all faster than "exponential" algorithms.

Big-O analysis becomes ridiculous once you get into non-polynomial time (very slow) algorithms.

n!   (n+1)!  n! is strictly faster.  n! = o ( (n+1)! )


For example (lg n)^k   = o (n^c), for c >0 and k >= 0.


lg (n)^1000000 = o (n).   lg(n)^1000000 = o (n^0.0001).

The lg function grows so slowly and its values are generally so low, that even raising to it large powers doesn't stop it from being FASTER than polynomial functions.


So, we say that n = Theta (100n)...but our current notation says that n = o (n lg n).  There is a school of thought that says that we shouldn't count logs anyway.  That n lg n, should be the same as n.

n is faster than n lg n, which is faster than n lg^2(n), which is faster than n lg^3 (n)...all of which are faster than n^1.000001.



Bubble Sort   n^2 time.   This takes all day.

Shell Short n lg^2 n time.  The difference between this and Tree Sort would have been largely unnoticeable.
Tree Sort     n lg n time.  Really fast.
Why Tree Sort and not Quick or Merge?  (ForTran).  ForTran has no recursion.






4^lg n     n^3



4^lg n = n^lg 4 = n^2