CODEWITHSUNDEEP
c#algorithmsortingtime-complexitybig-o
nevas
nevas

Reputation: 81

Can Someone please explain me the logic of calculating big-O in my example

It is said the complexity of selection sort is O(N^2) but i don't get the logic since i'm reducing the number of times the loop executed. I understand for Code block 2 but not for code block 1

public int[] Sorting(int[] array)
{
    for (i = 0; i <= array.Length - 1; i++)
    {           
        minimum=i;
        for (j = i; j < array.Length-1; j++) 
        {
            if (array[minimum] > array[j+1])
                minimum = j + 1;
        }   
        int temp = array[minimum];
        array[minimum] = array[i];
        array[i] = temp;
    }

    return array;
}

for(i=0;i<=n;i++) //Code 2
{
    for(j=0;j<=n;j++)

Upvotes: 3

Views: 100

Answers (1)

Orace
Orace

Reputation: 8359

Let n be the array size.

And look at the number of comparison (calls to if (array[minimum] > array[j+1])).

  • For i=0 it's called n-1 times.
  • For i=1 it's called n-2 times.
  • ...
  • For i=n-1 it's called 0 times.

Finally, it's called 0+1+...+(n-1) times.

It's the sum of consecutive integers.

And, in your case, it's (n-1)*n/2 which is O(n²)

Edit:

So the exact number of comparison is (n-1)*n/2, it's not exactly n², it's look better than n², but it's really not.

  • For n=10 you have 45 comparisons.
  • For n=100 you have 4950 comparisons.

That it, for 10 times more entry, you take > 100 times more times to complete your algorithm.

  • For n=10 you have 45 comparisons.
  • For n=1000 you have 499500 comparisons.

That it, for 100 times more entry, you take > 10 000 times more times to complete your algorithm.

As you can see, when you multiply by k the number of entry, you multiply roughly by k² the computation time.

Upvotes: 5

Related Questions