edited by
3,027 views
22 votes
22 votes

Consider the following recurrence relation:

$T(n)
= \begin{cases}
2T (\lfloor\sqrt{n}\rfloor)+ \log n & \text{if }n \geq 2   \\
 1& \text{if }n = 1   
\end{cases}$

Which of the following statements is TRUE?

  1. $T(n)$ is $O(\log n)$.
  2. $T(n)$ is $O(\log n \cdot \log \log n)$ but not $O(\log n)$.
  3. $T(n)$ is $O(\log^{3/2} n)$ but not $O(\log n \cdot \log \log n)$.
  4. $T(n)$ is $O(\log^{2} n)$ but not $O(\log^{3/2} n)$.
  5. $T(n)$ is $O(\log^{2} n \cdot \log \log n)$ but not $O(\log^{2} n)$.
edited by

3 Answers

Best answer
22 votes
22 votes

Let $n=2^k$

$T\left(2^k\right)= 2T\left(2^{k/2}\right) + k $           

Let $T\left(2^k\right)=S(k) \implies T\left(2^{k/2}\right) = S(k/2)$

$S(k)=2S(k/2)+k$

This gives $S(k) = \Theta(k \log k)$ (Master theorem case 2)

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

So ans is b

edited by
6 votes
6 votes

T(n)=T(√n)+log n

now put n=2 ,m=log n.........................(I)

then the equation is

T(2m)=T(2m/2)+m

Now, put T(2m)=S(m)

Now,equation becomes

S(m)=S(m/2)+m

here f(m)=m

and nloga=m

So, complexity will be O(m log m)

putting m value from equation (I) we get

Complexity T(n)= O(log n . log log n)

Ans will be (B)

0 votes
0 votes

$T(n)=2T(n^{1/2})+log (n)$

$T(n^{1/2})=2T(n^{1/4})+log (n^{1/2})$

$T(n^{1/4})=2T(n^{1/8})+log (n^{1/4})$

Now Back-Substituting:

$T(n)=2T(n^{1/2})+log (n)$

$T(n)=2(2T(n^{1/4})+log (n^{1/2}))+log (n)$

$T(n)=2^2T(n^{1/4})+2log (n^{1/2})+log (n)$

$T(n)=2^2(2T(n^{1/8})+log (n^{1/4}))+2log (n^{1/2})+log (n)$

$T(n)=2^3T(n^{1/8})+2^2log (n^{1/4})+2log (n^{1/2})+log (n)$

And it can be written as:

$T(n)=2^3T(n^{1/8})+3log(n)$

.

.

.

$T(n)=2^kT(n^{1/2^k})+klog(n)$

Now , for sake of simplicity I’ll consider T(2) = 1

$n^{1/2^k} = 2$

Taking log both sides

$log (n^{1/2^k}) = log 2$

$1/2k\hspace{1mm}log(n) = 1$

$log(n) = 2^k$

$k = loglog(n)$

Now substituting this into our answer :

$T(n)=2^{loglog (n)}+loglog(n) \hspace{1mm} log(n)$

$T(n)=log (n)+loglog(n) \hspace{1mm} log(n)$

And,

$log (n) < loglog(n) \hspace{1mm} log(n)$

So,

$T(n)=O(loglog(n) \hspace{1mm} log(n))$

Answer : B

edited by
Answer:

Related questions