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?

## Thanks again.

Posted via http://www.ruby-forum.com/.

Hi, Jason, the 0 is an uppercase letter ‘o’, it is called Big-O

notation. It

represents the manner in which the number of steps grow as the size of

the

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

reached,

if we were to graph the number of steps involved, it would be increasing

as

if it were squared.

In this case, n is the length of the array. So O(n^2) means that if you

cut

everything else out, the greatest impact to the number of steps follows

n*n

while the built in sort follows n * log(n)

There can be other factors, but when n gets large enough, the other

factors

don’t matter any more.

Why do we say that yours is O(n^2) instead of some other time

complexity?

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

end

So that is the first n, it goes through each of the n indexes in the

array.

But, for each of these indexes, it calls max_array_index, which also

goes

through the indexes, as you can see in

def max_array_index(array, size)

i = 1

while i < size do

…

i += 1

end

So, that is the second n. It will go through the n indexes in the

sort_array

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

rather

goes through 1 fewer than the previous iteration, each time, but given

this

knowledge, we can say that the actual time complexity would be closer to

n(n+1)/2, but that comes out to n*n/2 + n/2, and in Big-O notation, we*

are

just concerned with which factors have the greatest impact. You can see

the

nn/2 will grow much faster than n/2, so we ignore n/2. And you can see

that

squaring it’s value every time will cause it to increase much faster

than

dividing it by 2 will slow it’s increase, so we discard the coefficient

and

are just left with n*n, so it is O(n^2)

Hope that wasn’t too poorly worded.

-Josh