Big-O notation (was: Re: Python and Schools)
Christopher A. Craig
list-python at ccraig.org
Wed Apr 16 17:14:23 CEST 2003
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
More information about the Python-list
mailing list