# TIFR2015-B-1

1k 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)$.

edited
4

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

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$

0
Anyway I will write the whole answer tomorrow.

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
0

2

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

0
Yes Correct, $\log 2^{k} = k$.

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

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

1
667 views
Consider the following code fragment in the $C$ programming language when run on a non-negative integer $n$. int f (int n) { if (n==0 || n==1) return 1; else return f (n - 1) + f(n - 2); } Assuming a typical implementation of the language, what ... polynomial in $n$. This algorithm runs in polynomial time in $n$ and the optimal running time is polynomial in $n$. The algorithm does not terminate.
Consider the following undirected connected graph $G$ with weights on its edges as given in the figure below. A minimum spanning tree is a spanning tree of least weight and a maximum spanning tree is one with largest weight. A second best minimum spanning ... minimum spanning tree here. There is unique minimum spanning tree, however there is more than one second-best minimum spanning tree here.
Two undirected graphs $G_{1}=(V_{1}, E_{1})$ and $G_{2}= (V_{2}, E_{2})$ are said to be isomorphic if there exist a bijection $\pi: V_{1} \rightarrow V_{2}$ such that for all $u, v \in V_{1}, (u, v) \in E_{1}$ if and only $( \pi (u), \pi (v)) \in E_{2}$. Consider the ... (ii) $L$ is $NP$- hard. (iii) $L$ is undecidable. Only $(i)$ Only $(ii)$ Only $(iii)$ $(i)$ and $(ii)$ $(ii)$ and $(iii)$
Consider the following grammar (the start symbol is $E$) for generating expressions. $E \rightarrow T - E \mid T + E \mid T$ $T \rightarrow T * F \mid F$ $F \rightarrow 0 \mid1\mid 2\mid 3\mid 4\mid 5\mid 6\mid 7\mid 8\mid 9$ With respect to this grammar, which of the following trees is the valid evaluation tree for the expression $2*3*4 - 5*6+7$?