Question

An array A is of length n has log( n) distinct numbers.

What is the time complexity of sorting A by best comparison based algorithm ?

Comments

Sir I think Heap sort performs bettern with nearly (log n)²

---

count sort is not comparison based

---

wouldnot selection sort work best in this case?

Answer 1

We will use binary search tree kind of data structure (Heap Sort) to implement the operation of sorting..

Time complexity of Heap Sort for n items is O(n log n).

The time complexity for log (n) distinct elements will be O(n loglog n) ...

 

I am new to this platform so please correct me if am wrong..

Comments

I did in O(n) time.

As build heap requires theta(n) + deletion of each distinct element is O(logn)
And for logn elements logn*logn
So n+log^2(n)
=O(n)

---

@Deepak Pandey I think answer should be O(logn loglogn)