From: Josh Cheek <josh.cheek@...>
Date: 2009-10-13T12:22:47+09:00
Subject: Re: manually sort array of numbers

--000e0cd2be6e51480a0475c88f69
Content-Type: text/plain; charset=ISO-8859-1

On Mon, Oct 12, 2009 at 9:46 PM, Jason Lillywhite <
jason.lillywhite@gmail.com> wrote:

> Josh Cheek wrote:
>
> > First of all, the time complexity of your sort is O(n^2) while the built
> > in
> > sort's time complexity is O(n lg n)
>
> Wow. That is interesting. Thank you for sharing. I really just want to
> learn how to sort something on my own before using the Array#sort
> method. I learned to write this function in my intro to Java class at
> school.
>
> 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
n*n/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

--000e0cd2be6e51480a0475c88f69--