Question

$Thenumberofelementsthatcanbestored$
$in\Theta \left(logn\right)timeusingheapsortis$

• A. $\Theta \left(\frac{logn}{loglogn}\right)$
• B. $\Theta \left(1\right)$
• C. $\Theta \left(\sqrt{l}ogn\right)$
• D. $\Theta \left(logn\right)$

Answer 1

The correct option is A $\Theta \left(\frac{logn}{loglogn}\right)$

If we have an array of x elements then time complexity to sort x elements using heap sort is

$\Theta \left(xlogx\right)$

We need to find value of x so that time complexity to sort x elements gets

$\Theta \left(logn\right)$

we can direct discard option (a) and (d).

Now check option (c)

$=\Theta \left(\frac{logn}{log\log n}log\left(\frac{logn}{loglogn}\right)\right)$

$=\Theta \left(\frac{logn}{log\log n}\right(loglogn-logloglogn\left)\right)$

$=\Theta \left(logn\left(\frac{loglogn-loglogloglogn}{log\log n}\right)\right)$

$=\Theta \left(\log n\right)$