CODEWITHSUNDEEP
algorithmsortingtime-complexity
sam
sam

Reputation: 787

Why are only n/2 iterations considered for lower bound of selection sort?

From "Algorithms Unlocked" - Cormen, in Chapter 3- Algorithms for Sorting and Searching, under "Selection Sort".

The running time is Omega(n^2). This lower bound is calculated by considering n/2 iterations of the outer loop. Why n/2 iterations are considered?

Isn't the entire array traversed in all cases, including the lower-bound case? If yes, shouldn't 'n' be considered instead of n/2?

Edit1: That n/2 is considered even for the inner loop is not helping understand the logic.

Upvotes: 2

Views: 787

Answers (1)

dvorn
dvorn

Reputation: 3147

The logic is the following: Different iterations of outer loop have different lengths of inner loop. In the first n/2 iterations of the outer loop we know that the inner loop has length >= n/2. Thus, we know that total amount of work is greater than the amount of work for the first n/2 iterations which is greater than (n/2)*(n/2) = n^2/4, thus Omega(n^2).

If we considered entire outer loop, we would not be able to state that inner loop has much work to do because the last iteration of outer loop has inner loop of length 1, and we would get the estimate n*1.

For better understanding you should keep in mind the following two moments:

  1. Definition of Omega(n^2). It does not say that complexity is >= n^2. It says that there is a constant C such that complexity >= C * n^2. C might be equal 1, then >= n^2, or 100, then >= 100 * n^2, or 0.000001, then >= 0.000001 * n^2. But since we've found that for selection sort we have >= (1/4)*n^2, we know that selection sort is Omega(n^2) with C equal 0.25.

  2. In analyzing the complexity of selection sort we do not discuss "worst case" or "best case" scenarios. In fact, the algorithm does not depend on data we are sorting and it is always performing exactly the same iterations in outer and inner loops. (To be precise: the only difference, depending on the data, is whether we perform the swap operation or not. But we do not count the swap operation in the analysis.) Thus, when we are talking about "first n/2 iterations" of the outer loop, we do not assume that the algorism was able to complete the job in n/2 iterations. We just evaluate the amount of work done in the first n/2 iterations leaving the work in remaining iterations aside.

Upvotes: 3

Related Questions