Computing speed

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 ?

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!

Of course, as with all performance measurements in the real world, you can't treat existing APIs as a black box. Simply calling myList.get(i) might have an overhead of O(n) or O(lgN) (or something else) depending on how the list is implemented.
--Mark

[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 ]

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...