Big-O notation
Steven Taschuk
staschuk at telusplanet.net
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 telusplanet.net Mark: "Turn-about is fair play, sir."
-- _Mirror Dance_, Lois McMaster Bujold
More information about the Python-list
mailing list