CODEWITHSUNDEEP
c++sortingtime-complexitybig-oselection-sort
user4352513
user4352513

Reputation:

Step-by-step process of finding selection sort big theta notation

I'm having trouble figuring the process of finding the big theta notation for this selection sort sample. I've read online that and the tl;dr's that nested loops means it will = O(n^2)however, I don't know how they got it. I need a step by step process of finding the notation, i.e adding the cost of operations and everything. would be nice if someone did it for this sample code, so I can understand it more clearly. Thanks in advance...

void select(int selct[])
{
    int key;
    int comp;
    for (int i = 0; i < 5; i++)
    {
        key = i;
        for (int j = i + 1; j < 5; j++)
        {
            if (selct[key] > selct[j])
            {
                key = j;
            }
        }
        comp = selct[i];
        selct[i] = selct[key];
        selct[key] = comp;
    }
};

Upvotes: 0

Views: 583

Answers (1)

templatetypedef
templatetypedef

Reputation: 373012

When analyzing the time complexity of an algorithm, I actually find it helpful to not look at the code and to instead think about the core idea driving the algorithm. If you know conceptually what the algorithm is doing, it's often easier to figure out the time complexity by just thinking through what the algorithm is going to do and then deriving the time complexity from there.

Let's apply that approach here. So how exactly does selection sort work? Well, it starts off by finding the minimum value in the last n elements and swapping it to position 0, then finding the minimum value in the last n - 1 elements and swapping it to position 1, then finding the minimum value in the last n - 2 elements and swapping it to position 2, etc.

The "hard part" of the algorithm is figuring out which of the last n - k elements is the smallest. Selection sort does this by iterating over those elements and comparing each against the element that currently is known to be the smallest. That requires n - k - 1 comparisons.

Let's see how many comparisons that is. On the first iteration, we need to make n - 1 comparisons. On the second iteration, we make n - 2 comparisons. On the third, we make n - 3 comparisons. Summing up the number of comparisons gives us a good way of measuring the total work:

(n - 1) + (n - 2) + (n - 3) + ... + 3 + 2 + 1 = n(n - 1) / 2

This is a famous summation - it's worth committing it to memory - and tells us how many comparisons are required. The number of comparisons made is a great proxy for the total amount of work done. Since there are n(n - 1) / 2 = n2 / 2 - n / 2 = Θ(n2) comparisons made, the time complexity of selection sort is Θ(n2).

Upvotes: 1

Related Questions