Nick Delauney

Ranch Hand

Posts: 43

posted 14 years ago

I'm not sure if this is the same as the big oh question but, I want to know how exactly to compute speed of alogrithms. From my understanding you look for a loop and call it "n", if theres an inner loop you have "n2"(n squared). Where do things like nlogn come into play. Can anyone shed any light on how this is done ?

N.D:"Anything worth having, takes time to get"

Ilja Preuss

author

Sheriff

Sheriff

Posts: 14112

posted 14 years ago

You only get n*n if the inner loop runs as often as the outer loop *every time*. If you do the math, you will actually see that the body of the inner loop will be therefore executed n*n times - and that is where it is coming from!

Originally posted by Nick Delauney:

I'm not sure if this is the same as the big oh question but, I want to know how exactly to compute speed of alogrithms. From my understanding you look for a loop and call it "n", if theres an inner loop you have "n2"(n squared).

You only get n*n if the inner loop runs as often as the outer loop *every time*. If you do the math, you will actually see that the body of the inner loop will be therefore executed n*n times - and that is where it is coming from!

The soul is dyed the color of its thoughts. Think only on those things that are in line with your principles and can bear the light of day. The content of your character is your choice. Day by day, what you do is who you become. Your integrity is your destiny - it is the light that guides your way. - Heraclitus

Mark Herschberg

Sheriff

Posts: 6037

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 14 years ago

This is a bit of an overstatement. (I'm sure Ilja knows this, but for others' benefit...) Let's say the inner loop is searching for a particular element in an array, and it may be found anywhere from position 0 to position n-1, with equal probability. Then

Well, the n part can come from any loop, as noted. log n most commonly comes from recursing through some sort of tree structure or performing something like a binary search. Take a sorted array with 1024 elements. To search for a particular element, taking advantage of the fact the array is sorted, I might first look at element 512, decide my target is before that, look at 256, decide the target's before that too, look at 128, decide it's before that, then maybe 64, 96, 80, 88, 84, 82, 81. Each time, I'm narrowing the region to search by a factor of two. (Look at the sequence of differences in values I'm trying: 128, 64, 32, 16, 8, 4, 2, 1.) This algorithm will typically require up to 9 iterations to find an item, or log2(1024) - 1. (Where log2 is log base 2.) In general, this search will be O(log(n)) for an n-element array.

[ April 29, 2003: Message edited by: Jim Yingst ]

**[Ilja]: You only get n*n if the inner loop runs as often as the outer loop *every time***

This is a bit of an overstatement. (I'm sure Ilja knows this, but for others' benefit...) Let's say the inner loop is searching for a particular element in an array, and it may be found anywhere from position 0 to position n-1, with equal probability. Then

*on average*the inner loop will execute n/2 times, and the algorithm performance would be n^2/2. But we wouldn't include the /2 when using big-O notation; we'd just say the algorithm is O(n^2). Constant factors like this are routinely ignored.

**[Nick]: Where do things like nlogn come into play.**

Well, the n part can come from any loop, as noted. log n most commonly comes from recursing through some sort of tree structure or performing something like a binary search. Take a sorted array with 1024 elements. To search for a particular element, taking advantage of the fact the array is sorted, I might first look at element 512, decide my target is before that, look at 256, decide the target's before that too, look at 128, decide it's before that, then maybe 64, 96, 80, 88, 84, 82, 81. Each time, I'm narrowing the region to search by a factor of two. (Look at the sequence of differences in values I'm trying: 128, 64, 32, 16, 8, 4, 2, 1.) This algorithm will typically require up to 9 iterations to find an item, or log2(1024) - 1. (Where log2 is log base 2.) In general, this search will be O(log(n)) for an n-element array.

[ April 29, 2003: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, *Twister*

Ilja Preuss

author

Sheriff

Sheriff

Posts: 14112

posted 14 years ago

Of course I know this - thanks for the correction...
The soul is dyed the color of its thoughts. Think only on those things that are in line with your principles and can bear the light of day. The content of your character is your choice. Day by day, what you do is who you become. Your integrity is your destiny - it is the light that guides your way. - Heraclitus

Originally posted by Jim Yingst:

[Ilja]: You only get n*n if the inner loop runs as often as the outer loop *every time*

This is a bit of an overstatement. (I'm sure Ilja knows this, but for others' benefit...)

Of course I know this - thanks for the correction...