Question

Which of the following represents the number of elements that can be sorted in $\Theta \left(n\right)$ times using merge sort?

• A. $\Theta \left(n\right)$
• B. $\Theta \left(\frac{n}{logn}\right)$
• C. $\Theta \left(\sqrt{n}\right)$
• D. $\Theta \left(logn\right)$

Answer 1

The correct option is B $\Theta \left(\frac{n}{logn}\right)$

$Timecomplexitytosortnelementsusing$
$mergesort=\Theta \left(nlogn\right)$

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

$\Theta \left(n\right)=\Theta \left(\frac{n}{logn}\right[logn-loglogn\left]\right)$

$\Theta \left(n\right)=\Theta \left(\frac{n}{logn}logn\right)[logn-loglogn=(logn\left)\right]$

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