How to demonstrate bigO cost of algorithms?
Mitja
nun at meyl.com
Wed Jun 2 23:25:32 CEST 2004
Rusty Shackleford <rs at overlook.homelinux.net>
(news:slrncbs3d0.9l3.rs at frank.overlook.homelinux.net) wrote:
> Thanks for that explanation -- it really helped. I forgot that O(n)
> can translate into dn + c where d and c are constants.
???
You'd NEVER write, e.g., O(n)=3n+7. What you'd say would be simply O(n)=n.
As already pointed out, this means that complexity (and, with that,
execution time) is PROPORTIONAL to n. It doesn't give you the number of
seconds or something.
Consider the following:
def foo(n):
for i in range(n):
for j in range(i):
print i, j
The "print" statement is executed n*n/2 times. However, O(n)=n^2: if you
increase n seven times, the complexity increases 49 times.
>
> I think I'm going to keep trying to figure out ways to demonstrate
> big O stuff, because I just don't understand it until I see it in a
> non-abstract sense.
>
> Thanks again.
More information about the Python-list
mailing list