Big-O notation (was: Re: Python and Schools)

[Christopher A. Craig]

Erik Max Francis <max at alcyone.com> writes:

> It also means that one doesn't bother distinction between logarithms
> base 10, e, 2, etc.; O(ln n) ~ O(lg n) ~ O(lb n).  Similarly, O(2^n) ~
> O(10^n) ~ O(e^n) too.

The second part of this isn't true.  If a process f(n) has a running
time T(N) for in input of size N, said process is O(N) if there exist
constants "k" and "j" such that O(N)*k <= T(N) for all N>=j

While there does exist a constant (log(A)/log(B)) for which
log_A(N)*k <= log_B(N) for all sufficiently large N, there is
no constant for which (A**N)*k <= B**N for all sufficiently large N
when B>A.

-- 
Christopher A. Craig <list-python at ccraig.org>
"Never let schooling get in the way of your education"  Mark Twain