CODEWITHSUNDEEP
algorithmsortingtime-complexityselection-sort
Sara Hamzah
Sara Hamzah

Reputation: 3

how can calculate time complexity of selection sort step by step?

enter image description here I should solve the time Complexity method like this photo but I have a problem solving it for selectio sort. I solved it in general and not in detail like I wanted going to know the solution method and not just like (T(n)= O(n-1)+..+1. I want it to be step by step how we reached this answer and how we produced the time (O(n^2)). This is the code that I made through which I want to know the time complexity: package example;

public class Main1 {

public static void main(String[] args) {

    int arr[] = { 71, 2, 15, 43, 1, 30, 8 };
    selectionSort(arr);
    System.out.print("[ ");
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ,");
    }
    System.out.print(" ]");
}

static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[min] > arr[j]) {
                min = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }

}

}

Upvotes: 0

Views: 66

Answers (1)

trincot
trincot

Reputation: 350781

For selection sort the task is much easier than for merge sort, for the following reasons:

  • Contrary to merge sort, selection sort does not apply recursion, so you don't actually work with a recurrence relation 𝑇(𝑛).

  • Contrary to merge sort, the number of iterations made by selection sort does not depend on the result of data comparisons, but only on the size of the array. So with selection sort there is no concept of worst case, best case: all cases are equal.

Analysis

The two (nested) loops in selection sort are really visiting all possible pairs of (𝑖, 𝑗), where 0 ≤ 𝑖 < 𝑗 < 𝑛. So the inner if statement is executed as many times as there are such pairs (𝑖, 𝑗).

This number is equal to "𝑛-choose-2", i.e. a binomial coefficient, and it is equal to 𝑛(𝑛−1)/2.

Whether or not the body of the if statement is executed is not relevant for time complexity analysis, since that assignment to min has a time complexity of O(1), just like the evaluation of the if condition. So for one execution of the whole if statement, we either have O(1) or O(1+1), which still is O(1), either way.

The three swap instructions also have a O(1) time complexity and are executed 𝑛−1 times.

There is also the overhead of evaluating the outer for initialisation and exit.

Adding all that together we have this time complexity:

θ(1) + θ(𝑛−1) + θ(𝑛(𝑛−1)/2) = θ(𝑛²).

Upvotes: 0

Related Questions