Big-O notation

Steven Taschuk staschuk at
Wed Apr 16 23:53:16 CEST 2003

Quoth Duncan Booth:
> I believe you are making some unreasonable assumptions here. Remember that 
> if I have an algorithm that is O(N^2) that is really just a shorthand for 
> saying that it will have a running time a*N^2 + b*N * c where a, b, and c 
> are constants but for sufficiently large N only the N^2 term matters.

Not to dispute your general point, but a nit: O(n^2) doesn't imply
a polynomial expansion such as you have above; the actual runtime
could be, for example, 3n^2 + log n + 18/n.  That is, the
additional terms might be anything which (asymptotically) grows
slower than n^2.

Steven Taschuk              Aral: "Confusion to the enemy, boy."
staschuk at    Mark: "Turn-about is fair play, sir."
                             -- _Mirror Dance_, Lois McMaster Bujold

More information about the Python-list mailing list