CODEWITHSUNDEEP
sortingselection
rohit15079
rohit15079

Reputation: 213

How To calculate time complexity of selection sort

Time complexity of Selection Sort(Worst case) using Pseudocode:

'Selection-Sort(A)

1 For j = 1 to (A.length - 1)

2   i = j

3   small = i

4   While i < A.length

5     if A[i] < A[small]

6       small = i

7     i = i + 1

8   swap A[small], A[j]

First step will occur n-1 times (n is length of array). So the second and third. I am stuck with 4th step whether it will occur n! times or something else.

Upvotes: 1

Views: 22671

Answers (1)

Humza
Humza

Reputation: 378

The basic operation for this algorithm is the comparison at line 5, in the inner loop. Both loops are executed ≈ n times, i.e. the basic operation is executed n*n times ≈ n^2.

The time complexity for selection sort is O(n^2). It is same for worst best and average cases.

You should have look at the link below it gives a good rundown on selection sort. https://www.khanacademy.org/computing/computer-science/algorithms/sorting-algorithms/a/analysis-of-selection-sort

Hope this helps.

edit:

When analyzing the time complexity of non recursive algorithms,

  • Decide on parameters indicating the input size
  • Identify the basic operation
  • Set up a sum indicating the number of times the basic operation is executed
  • Establish its order of growth
  • Give an asymptotic estimation

In this case the input size will be the size of the array, the basic operation is of comparison, the arithmetic sum would be,

Σ1≤ j ≤n-1 Σj≤ i ≤n or Σ0≤ j ≤n-2 Σj+1≤ i ≤n-1

This will evaluate to (n-1)(n/2) which is asymptotically O(n^2).

For more information i would recommend these two books,

  1. Introduction to Design and Analysis of Algorithms - Anany Livitin

  2. Introduction to Algorithms - Coreman

Upvotes: 2

Related Questions