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).**

21 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?

- $T(n)$ is $O(\log n)$.
- $T(n)$ is $O(\log n. \log \log n)$ but not $O(\log n)$.
- $T(n)$ is $O(\log^{3/2} n)$ but not $O(\log n. \log \log n)$.
- $T(n)$ is $O(\log^{2} n)$ but not $O(\log^{3/2} n)$.
- $T(n)$ is $O(\log^{2} n. \log \log n)$ but not $O(\log^{2} n)$.

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

Please, help.

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

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

Now, proceed accordingly, you are following the right procedure.

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$

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

20 votes

Best answer

6 votes

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

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

then the equation is

T(2^{m})=T(2^{m/2})+m

Now, put T(2^{m})=S(m)

Now,equation becomes

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

here f(m)=m

and n^{log}a^{b }=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 m^{log}a^{b }=1

m>1...

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

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 n^{lo}^{gba }// n^{log22}=n

case 1 ) if n^{lo}^{gba }>f(n) then TC=O(n^{lo}^{gba})

case 2) if n^{lo}^{gba }<f(n) then TC=O(f(n))

case 3) if n^{lo}^{gba }=f(n) then TC=O(f(n)logn) or O(n^{lo}^{gba }logn) same thing as both are of same order.

here we're comparing n^{lo}^{gba }and f(n) in terms of their order , not actual mathematical value.