Question

The asymptotic upper bound solution of the recurrence relation given by

$T\left(n\right)=2T\left(\frac{n}{2}\right)+\frac{n}{logn}is$

• A. O(log log n)
• B. O(n log n)
• C. $O\left(n^2\right)$
• D. O(n log log n)

Answer 1

The correct option is D O(n log log n)

We will apply master theorem in this question:

a = 2, b = 2 and k = 1 and p =-1.
We will compare a and $b^k$
i.e.,

$2=2^1$ and we have p = - 1

$ThenT\left(n\right)=⊝\left(n^{lo{g}_{2}2}loglogn\right)$

$T\left(n\right)=⊝\left(nloglogn\right)$

$and⊝\left(nloglogn\right)>O\left(nloglogn\right)$

So, option (C) is correct.