On Mon, Oct 12, 2009 at 9:46 PM, Jason L. <
[email protected]> wrote:
What does the zero in “O(n^2)” mean and how did you figure that out?
Posted via http://www.ruby-forum.com/.
Hi, Jason, the 0 is an uppercase letter ‘o’, it is called Big-O
represents the manner in which the number of steps grow as the size of
problem increases. O(n^2) means that the number of steps grows in a
quadratic fashion. In other words, after some given value of n is
if we were to graph the number of steps involved, it would be increasing
if it were squared.
In this case, n is the length of the array. So O(n^2) means that if you
everything else out, the greatest impact to the number of steps follows
while the built in sort follows n * log(n)
There can be other factors, but when n gets large enough, the other
don’t matter any more.
Why do we say that yours is O(n^2) instead of some other time
Well if you look at the algorithm, you can see that in the sort_array
function, you have
i = 0
while i < array.length do
i += 1
So that is the first n, it goes through each of the n indexes in the
But, for each of these indexes, it calls max_array_index, which also
through the indexes, as you can see in
def max_array_index(array, size)
i = 1
while i < size do
i += 1
So, that is the second n. It will go through the n indexes in the
function, and for each of these indexes, goes through the indexes in the
mas_array_index function. So it is n*n, or n^2.
Now, there are other steps in there, too, but they aren’t really that
important when the size of the array gets large. And yes, the
max_array_index function doesn’t go through all of the indexes, but
goes through 1 fewer than the previous iteration, each time, but given
knowledge, we can say that the actual time complexity would be closer to
n(n+1)/2, but that comes out to nn/2 + n/2, and in Big-O notation, we
just concerned with which factors have the greatest impact. You can see
nn/2 will grow much faster than n/2, so we ignore n/2. And you can see
squaring it’s value every time will cause it to increase much faster
dividing it by 2 will slow it’s increase, so we discard the coefficient
are just left with n*n, so it is O(n^2)
Hope that wasn’t too poorly worded.