Re: An informal introduction to O(N) notation

in reply to Re: An informal introduction to O(N) notation
in thread An informal introduction to O(N) notation

Actually, a year is less than 2^55 nanoseconds. And I wouldn't call a set with 55 elements "huge". Beware of the power of exponentation. Your computer needs to speed up with a factor of 1000 to be able to increase your dataset with no more than 10 so that it will run in the same time....

Abigail

Comment on Re: An informal introduction to O(N) notation

Replies are listed 'Best First'.
Re: Re: An informal introduction to O(N) notation by theorbtwo (Prior) on Jan 18, 2003 at 21:40 UTC
Sigh. That's what I get for not checking my arithmetic. You're right, of course. I stand corrected on this example, but if you change the example to be O(1) at 1 year vs. O(N^2) at 1ns*N^2, the size of the dataset for the second to become slower becomes a lot larger. (Specificly, around 178 million items.) Also, there's the consideration of O() notation being the worst-case senerio. For example, even though bubble-sort is O(N^2), for nearly-sorted input, it can be quit efficent. Warning: Unless otherwise stated, code is untested. Do not use without understanding. Code is posted in the hopes it is useful, but without warranty. All copyrights are relinquished into the public domain unless otherwise stated. I am not an angel. I am capable of error, and err on a fairly regular basis. If I made a mistake, please let me know (such as by replying to this node).	[reply]

Replies are listed 'Best First'.

Re: Re: An informal introduction to O(N) notation
by theorbtwo (Prior) on Jan 18, 2003 at 21:40 UTC

Sigh. That's what I get for not checking my arithmetic. You're right, of course. I stand corrected on this example, but if you change the example to be O(1) at 1 year vs. O(N^2) at 1ns*N^2, the size of the dataset for the second to become slower becomes a lot larger. (Specificly, around 178 million items.) Also, there's the consideration of O() notation being the worst-case senerio. For example, even though bubble-sort is O(N^2), for nearly-sorted input, it can be quit efficent.

Warning: Unless otherwise stated, code is untested. Do not use without understanding. Code is posted in the hopes it is useful, but without warranty. All copyrights are relinquished into the public domain unless otherwise stated. I am not an angel. I am capable of error, and err on a fairly regular basis. If I made a mistake, please let me know (such as by replying to this node).

[reply]

In Section Meditations