The Gateway to Computer Science Excellence
+20 votes
746 views

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. \log \log n)$ but not $O(\log n)$.
  3. $T(n)$ is $O(\log^{3/2} n)$ but not $O(\log n. \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. \log \log n)$ but not $O(\log^{2} n)$.
in Algorithms by Boss (30.7k points)
edited by | 746 views
+3

Remarks:
$1. log^2n = logn*logn$
$2. logn*loglogn > logn$
$3. logn*logn > logn*loglogn$
$4. logn*\sqrt{logn} > logn*loglogn$
$5. log^{3/2}n = logn*\sqrt{logn}$
$6. logn*logn*loglogn > logn*logn$
 

Correct option is (B).

0
Can anyone point out the mistake?

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

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

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

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

.

.

.

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

------------------------------------------------------------------------------

In initial equation put n=2

$T(2)=2T(1)+log (1))$

$T(2)=2$

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

Then k=$log(log(n))$

put  k in T(n)

$T(n)=log(n)*2+log(log(n))*log(n)$

So, this equals $O(log(n))$

Please, help.
0
Bhai you aren't using brackets correctly.

In line $1$ $\log n$ is outside the bracket and not inside.

Now, proceed accordingly, you are following the right procedure.
+1
@jeet  That was a typo. Ignore that. I have corrected it now. But problem still exist.
0
Yes bhai, so the mistakes is:

$1.$ It should be $\mathrm{k-1}$ not $\mathrm k$.

Also, I don't think it will come $3\log n$
0

$\begin{align} \mathrm {T(n)} &= 2\mathrm{T(n) + \log n}\\&=2  \{ \mathrm {2T(n^{\frac{1}{2^2}}+ \log \sqrt n)\}+\log n} \\&=\vdots \;\;\;\;\;\;\;\;\;\;\vdots\\&=\mathrm {2^{k-1}T(n^{\frac{1}{2^{k-1}}})+\cdots\cdots+\log n^{\frac{1}{2}} + \log n} \end{align}$

Can you proceed from here?

@Akash Papnai

0
The changes you did doesn't change my result though. @jeet
0
No it will change for sure.

For inner part you will get $\log \log n$ and outer part $\log n$

Which is the required answer.
0
Anyway I will write the whole answer tomorrow.

2 Answers

+18 votes
Best answer

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

by Boss (31.4k points)
edited by
0

T(2k-1) please explain

+2

if we take n=2k then T(2k) = 2T(2k/2) + log 2k. Right??

+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)

by Veteran (118k points)
0

See here a=1 b=2 and c=m

so according to master theorem  mloga=1

m>1...

so it would be O(m) not O(mlogm)!!!!!

0
@srestha

how did u get  O(m logm) by applying masters?

can u elaborate that part ?
0
T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

here T(n)=2T(n/2)+n so a=b=2 and f(n)=n

first evaluate nlogb// nlog22=n

case 1 ) if nlogba >f(n) then TC=O(nlogba)

case 2) if nlogba <f(n) then TC=O(f(n))

case 3) if nlogba =f(n) then TC=O(f(n)logn)   or O(nlogba logn) same thing as both are of same order.

here we're comparing  nlogband f(n) in terms of their order , not actual mathematical value.

0
@srestha

the question is

2T(root(n)⌋)+logn

you have solved for T(root(n)) + log n

and for that it will be theta(m) = theta (log n)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,252 answers
198,061 comments
104,698 users