CODEWITHSUNDEEP
algorithmsortingmathruntimetime-complexity
siddstuff
siddstuff

Reputation: 1255

Number of element which can be sorted using heapsort?

i faced a very confusing problem in the examination and attempted it wrong, it was an objective type problem, given four options , Now i know the correct option but i have no explanation.

Problem :

Number of elements which can be sorted in Ɵ(logn) time using heapsort is

a) Ɵ(1)

b) Ɵ(√ log n)

c) Ɵ(log n / loglog n)

d) Ɵ(log n)

Option c is correct.

i had selected the the option a), i thought in log n time only one element will be sorted, it was wrong, i don't know why option c) is correct.

Upvotes: 2

Views: 1429

Answers (2)

G. Bach
G. Bach

Reputation: 3909

Ignoring the fact that the question asks for a Theta bound on heap sort, which it doesn't have in the general case, here is why this is confusing:

When dealing with Landau notation (= O, Ɵ, Omega stuff), we are used to be given the input size as n; what you're being asked here is "what do we have to set the input size to to get a complexity of Ɵ(log n)".

For example: consider list traversal; this will take you O(n) for lists of size n. On the other hand, if we limit the input to log n for some n, we get a complexity of O(log n). Transferring this idea to sorting algorithms, we know that heap sort has a worst case complexity of O(n log n) if we give it a list of size n. So what happens if we give it a list of size log n? The complexity becomes less: we go from (n) log (n) to

(log n) log (log n) = log n log log n

Now to explain why c) was the right answer, I'll write l(n) instead of log n to make it slightly more readable.

Adjust the input size in the term n * l(n) to l(n)/l(l(n)) which is what c) states. We then get:

l(n)/l(l(n)) * l(l(n)/l(l(n)))
= l(n)/l(l(n)) * [l(l(n) - l(l(l(n)))]
= l(n) - [l(n) * l(l(l(n)))]/l(l(n))

As you can see (hopefully), the dominating term is l(n) = log n, so for inputs of the size l(n)/l(l(n)), heap sort has a worst case complexity of O(log n). The Theta however is definitely wrong for the general case.

Side note: does anyone know how to make the terms pretty? I know we don't have LaTeX inline here, but this doesn't look nice at all.

Upvotes: 2

MvG
MvG

Reputation: 60858

Let t=exp(n) be the time you have, and m be the number of items you can sort in that time.

a) m = Θ(1) ⇒ t → ∞: You can only sort a finite number of items, no matter the time.
b) m = Θ(√t) ⇒ t = Θ(m²): you need quadratic time. Stupid bubble sort.
c) m = Θ(t/log t) ⇒ t = Θ(m log m): this is the complexity you know for heap sort.
d) m = Θ(t) ⇒ t = Θ(m): linear time sorting is too good to be true.

I must confess that the conversion for c) is mostly based on “gut feeling”. I'm reasonably confident that it is right or at least “almost correct”, but I don't know the formal rules I used to show this.

Upvotes: 0

Related Questions