retagged by
27,872 views
113 votes
113 votes

The number of elements that can be sorted in $\Theta(\log n)$ time using heap sort is

  1. $\Theta(1)$
  2. $\Theta(\sqrt{\log} n)$
  3. $\Theta(\frac{\log n}{\log \log n})$
  4. $\Theta(\log n)$
retagged by

8 Answers

1 votes
1 votes

Option c:Time taken to sort logn/loglogn elements 

=logn/loglogn   * log(logn/loglogn   )

=logn *loglogn-logn*logloglogn /(loglogn)

=logn - logn*logloglogn /(loglogn)

second term is   (logn*(logy /y)) where y=loglogn    and logy/y <<1  so second term is <<logn, second term can be ignored

=O(logn)

1 votes
1 votes
@ Arjun Sir . I have tried to do like this. Please point out the error if any

Worst case time complexity of quick sort =O(nlogn)

O(nlog n) time -        n elements

Taking 'log' on both sides

log (nlog n) = log n

->  log n + log log n = logn

-> O(log n) = log n - log log n

 O(log n) =  log n /log log n elements

  Hence option C. Please check it.
1 votes
1 votes

Using heap sort to n elements it will take O(n log n) time.
Time complexity of heap sort is k log k.
Now put k = logn 
Now there are log n/ log log n elements in the heap.

So, Θ((logn/ log log n)log(logn/log log n))
= Θ(logn/log logn (log logn - log log logn))
= Θ((log n/log logn) × log log n)
= Θ (log n)
Trial and error method of all options
Hence, option (C) is correct answer.

reshown by
0 votes
0 votes
Here time complexity is given O(logn)

Now we have to calculate for the given input which time complexity is O(logn)

For heap sort the time complexity is O(xlogx)   [We take n as x to avoid confusion]

check for option a)

x=1;so time complexity is O(1)

check for option b

x=$\sqrt{logn}$ then time complexity is   $O(\sqrt{logn}log\sqrt{logn}$

check for option d

x=logn then time complexity is O($O({logn}log{logn}$)

So we can easily eliminate those options so answer is option c.

For sure we check option c

x=$\frac{logn}{loglogn}$   then time complexity is $\frac{logn}{loglogn}*log( \frac{logn}{loglogn})$

=$\frac{logn}{loglogn}*loglogn-\frac{logn}{loglogn}*logloglogn$      if n is large we can simply ignore the second term

=O(logn)
Answer:

Related questions

37 votes
37 votes
2 answers
1
Arjun asked Sep 23, 2014
9,943 views
Which one of the following is the tightest upper bound that represents the number of swaps required to sort $n$ numbers using selection sort?$O(\log n$)$O(n$)$O(n \log n$...
2 votes
2 votes
4 answers
2
Bikram asked Oct 4, 2016
595 views
Is an array that is sorted in decreasing order a max-heap?always yesalways nosometimes onlyyes but not in presence of duplicates
0 votes
0 votes
1 answer
3
Ramayya asked Jan 7
176 views
Worst case time complexity of heap sort for n elementsO(nlogn)O(logn)O^2O(n)