How to find the time complexity of recursive selection sort?

Question

Hey guys i have a quiz tommorow i am facing some problems finding time complexity of recursive programm of selection sort can any one explain how is it n^2. And also one more question that some sorting algorithms loops have n/2 time complexity what is the meaning of /2 sorry for newbie question.

#include <iostream>
using namespace std;

// recursive function to perform selection sort on subarray arr[i..n-1]
void selectionSort(int arr[], int i, int n)
{
    // find the minimum element in the unsorted subarray[i..n-1]
    // and swap it with arr[i]
    int min = i;
    for (int j = i + 1; j < n; j++)
    {
        // if arr[j] element is less, then it is the new minimum
        if (arr[j] < arr[min])
            min = j;    // update index of min element
    }

    // swap the minimum element in subarray[i..n-1] with arr[i]
    swap(arr[min], arr[i]);

    if (i + 1 < n)
        selectionSort(arr, i + 1, n);
}

Possible duplicate of [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) — user0042, Oct 15 '17 at 16:56
`selectionSort(arr, 0, n)` would make `n` comparisons in its loop. Then it would call `selectionSort(arr, 1, n)` which would make additional `n-1` comparisons, and call `selectionSort(arr, 2, n)` that would make `n-2` comparisons more, and so on. We leave calculating a sum of this arithmetic progression as an exercise for the reader. — Igor Tandetnik, Oct 15 '17 at 16:58
A compexity of `n/2` makes no sense, as the big-O notation is indifferent to a constant multiplier. `O(n/2) == O(n)` — Igor Tandetnik, Oct 15 '17 at 17:01
in the itterative algo of selection sort there is one value n/2(n-1) what is the meaning of this can u explain thank u@IgorTandetnik — Ahsan Ali, Oct 15 '17 at 17:03

Dúthomhas · Accepted Answer · 2017-10-15T18:53:33.950

Finding time complexity is often described in a way that is not really very helpful. Here is how it works for Selection Sort.

passes
The very first time through the algorithm, you must scan all n elements of the data.

The very next time through (on recursion), you must scan all but one, which is (n-1).

And so on. We can write the number of times we look at/compare an element as:

n + (n-1) + (n-2) + ... + 2 + 1

(You can quibble about that last term, but for simplicity here we just won't care. You'll see why in just a second.)

math identities
This particular series (notice all the additions) is called an “arithmetic progression”. The difference between each term is 1. The first term is n and the last term is 1 (or 2, whatever).

And using some math most people don’t remember (or weren’t taught) in High School, we can rewrite that sum as:

n(n+1)
──────
  2

(Yes, again, that last term is actually supposed to be a two, even though I’ve left it at one.)

as n grows arbitrarily large
Big O doesn’t care much about friendly values of n. It cares about what happens when n gets arbitrarily big. We say “n grows towards infinity”.

As it does, we can notice two things happening:

That division by 2 becomes insignificant: ∞/2 → ∞
That addition by 1 (or whatever) is also insignificant: ∞(∞+1) → ∞(∞)

So ultimately, we have ~~infinity~~, er, n multiplied by itself. The equation simplifies to:

n(n+1)
──────  →  n²
  2

complexity bounds
The worst case behavior is n², so we annotate that as “O(n²)”. But notice that the best case is also n². We annotate that as “Ω(n²)”. Finally, since the best and worst case behaviors are the same, we have a very nice tight bound on the behavior of the function. We annotate this as “Θ(n²)”.

Hence, selection sort has Θ(n²) complexity.

holy quiznak! I’m supposed to do this myself!!?
Yes, unfortunately, figuring out complexity is one of those things that people treat as if it were really easy — even when they don’t understand it well themselves. It takes some familiarity with math and some practice. The typical response is as in the links provided you above: ‘look at these common cases and choose the one that most closely matches’. I personally find that less satisfyingly instructive. It is also one of those things that university professors expect you to pick up right away.

My advice: don’t worry too hard. Do your best to understand the underlying principles. What we are doing is finding a function (like y=x²) that represents an algorithm’s behavior whenever its input is really large (n → ∞).

Being able to follow through the paths that the algorithm takes and recognizing when those paths are expensive is a more important ability than being able to come up with a mathematician’s answer. If you really need it you can always find a mathematician to help, either at the university or on the internet if you ask in the right places.

And, of course, feel free to take time to try to understand better and practice. Being able to do it right is a valuable skill, regardless of whether others see it.

:O)

You are awesome sir just awesome thank u so much @Dúthomhas — Ahsan Ali, Oct 15 '17 at 19:14

How to find the time complexity of recursive selection sort?

1 Answers1