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

[Erik Max Francis]

"Christopher A. Craig" wrote:

> Erik Max Francis <max at alcyone.com> writes:
> 
> > 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.

[scribbles on paper]

Right you are, thanks for that important correction.  The ratio of two
logarithmic functions with different bases is a constant, but the ratio
of two exponential functions with different bases is a different
exponential function, e^(k n), where k is the difference in the natural
logarithms of the two original bases.  So indeed, O(a^n) !~ O(b^n) for a
!= b.

Good catch!

-- 
 Erik Max Francis / max at alcyone.com / http://www.alcyone.com/max/
 __ San Jose, CA, USA / 37 20 N 121 53 W / &tSftDotIotE
/  \ The only source of knowledge is experience.
\__/ Albert Einstein
    Bosskey.net / http://www.bosskey.net/
 A personal guide to online multiplayer first person shooters.