Re^2: A script with a loop is running my computer Out of memory

O(log n) => work increases logarithmically as n grows. (ie, work increases, but at a rate slower than the growth of n.)

That's a pretty vague description of log(n)...

An exact description of log(n) is: for every multiplication of n with a constant factor (like doubling, or 10-fold increase), a fixed amount of extra work gets added.

Comment on Re^2: A script with a loop is running my computer Out of memory

Replies are listed 'Best First'.
Re^3: A script with a loop is running my computer Out of memory by davido (Cardinal) on Feb 08, 2011 at 08:56 UTC
That is better. We might also change "a fixed amount of extra work gets added" to "a single unit of extra work gets added." Even that is probably more vague than just coming to an understanding of what logarithmic graphs look like as 'n' increases. Unfortunately, that's sort of difficult to post here. I do like trying to improve the description though. Wikipedia has a great writeup on Big-O notation. Why didn't we have that when I was in college? ;) Dave	[reply]

Replies are listed 'Best First'.

Re^3: A script with a loop is running my computer Out of memory
by davido (Cardinal) on Feb 08, 2011 at 08:56 UTC

That is better. We might also change "a fixed amount of extra work gets added" to "a single unit of extra work gets added." Even that is probably more vague than just coming to an understanding of what logarithmic graphs look like as 'n' increases. Unfortunately, that's sort of difficult to post here. I do like trying to improve the description though. Wikipedia has a great writeup on Big-O notation. Why didn't we have that when I was in college? ;)

Dave

[reply]