edited by
4,836 views
15 votes
15 votes

Suppose you are given $n$ numbers and you sort them in descending order as follows:

First find the maximum. Remove this element from the list and find the maximum of the remaining elements, remove this element, and so on, until all elements are exhausted. How many comparisons does this method require in the worst case?

  1. Linear in $n$.
  2. $O\left ( n^2 \right )$ but not better.
  3. $O\left (n \log n \right )$
  4. Same as heap sort.
  5. $O\left ( n^{1.5} \right )$ but not better.
edited by

3 Answers

Best answer
20 votes
20 votes

The given procedure resembles something like Bubble sort or Selection Sort.
Every time, for every input it will take $O(n^2)$ so, B is the answer.

If you are thinking about heap sort,   where in the procedure, it is talked about building a heap? You can do extract_max only on a heap. Right ? The procedure is nearly same as bubble sort or selection sort.

Read question again: "First find the maximum. Remove this element from the list and find the maximum of the remaining elements, remove this element, and so on, until all elements are exhausted."

Just follow the steps. Find max, take it to right side of array. Shift.
So $n-1$ comparisons & $n-1$ shifts in the worst case.
Total  $n-1+n-2+n-3+....+1  + n-1+n-2+n-3+..+1 $     which is $O(n^2)$
Only number of comparisons is asked... which is also $\mathbf{O(n^2)}$

edited by
3 votes
3 votes
well it is given that we have to follow the same procedure as stated . so i think it will be option b not better than O(n2).

for first n comparision in worst case then (n-1) thn (n-2) till it becomes 1.

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

O(n2).
3 votes
3 votes
Initially to sort the list and arrange in the descending order T(n)=O(n2)

COMPARISONS:

ELEMENTS                    NO OF COMPARISONS

N                                        N-1

N-1                                     N-2

N-2                                     N-3

.

.

.

2                                     1

1                                     0

 

HENCE TOTAL NO OF COMPARISONS ARE

1+2+...+(N-2)+(N-1)

W.K.T  

1+2+..........+N =   [   N     ( N+1 )   ]  /  2

HENCE PUT N=N-1

[(N-1) (N-1+1) ] / 2 = [ N ( N-1) ] / 2

THUS T(N) IS ORDER OF N2

To delete an element,it take constant time
Answer:

Related questions