GATE CSE 2014 | Set 2 | Question: 13

Question

Which one of the following correctly determines the solution of the recurrence relation with $T(1) = 1$?

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

• A. $\Theta(n)$
• B. $\Theta(n\log n)$
• C. $\Theta(n^2)$
• D. $\Theta(\log n)$

Comments

Someone plz explain it...It is given in Coreman book of Algorithms that Master theorem cannot be applied to T(n)=2T(n/2)+nlgn because g(n)=n and f(n)=nlgn are not polynomially comparable.....

So can we apply master theorem in above question....?

---

Yes we can compute by that approach but this is a recurrence relation that means to compute T(1000) we need to know T(500)...for T(500) we need to know T(250)....for large n,  a large no of values have to be computed...

?

---

Bro see, ur aul is ur ssuming nlog here its logn, so logn is defenitely polynomialy smaller than n logn = O(n^(1-e)) where e is between 0 and  so yes maser theoem appleis

---

Done ✅

Answer 1

$f(n) =  \log n$

$a = 2, b = 2 \implies n^{\log_b a} = n$

So, $f(n) = \log n = O\left(n^{1-\epsilon} \right)$, we can take any $\epsilon$ from $0$-$1$ for example $0.5$ which gives $\log n = O(\sqrt(n))$, proof of which is given here: http://math.stackexchange.com/questions/145739/prove-that-logn-o-sqrtn

So, Master theorem Case 1, and answer will be $O\left(n^{\log_2 2}\right) = O(n)$

---

Alternate way:

$T(1) = 1 \\ T(2) = 2T(1) + \log 2 = 3 = 3n - 2\\T(4) = 2T(2) + \log 4 = 8 = 3n - 4 \\T(8) = 2T(4) + \log 8 = 19 = 3n - 5\\ T(16) = 2T(8) + \log 16 = 42 = 3n - 6$

The second term being subtracted is growing at a lower rate than the first term. So, we can say $T(n) = O(n)$.

Correct Answer: $A$

Comments

@Arjun Sir: I have some some confusion if we can apply master theorem here. From CLRS: "In the first case, not only must f(n) be smaller than n^log_ba, it must be polynomially smaller. That is,f(n) must be asymptotically smaller than n^log_ba a by a factor of n^ͼ for some constant ͼ > 0". 

In our case f(n) = lg n and n^log_ba = n. So (lg n)/n < n^ͼ holds for some ͼ > 0 ?

I tried plotting graphs for ͼ=0.5 and it seems that the inequality holds, but how to prove it without graph?

---

I had given for $\epsilon = 0.5$ rt?

---

That proves that log n is asymptotically smaller than n^1/2, but says nothing about it being polynomially smaller.

---

For that we already have a polynomial factor between $n$ and $n^{0.5}$

---

clrs page 57:

---

$T(\frac{n}{2}) = 2T(\frac{n}{4})+log(\frac{n}{2})$

                       $=2T(\frac{n}{4})+log(n)-1$

$T(\frac{n}{4}) = 2T(\frac{n}{8})+log(\frac{n}{4})$  

                         $  =2T(\frac{n}{8})+log(n)-2$

$T(\frac{n}{8})  =2T(\frac{n}{16})+log(n)-3$

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

$T(n) = 16T(\frac{n}{16})+15log(n) -34 $

.
.

$T(n) = 2^{k} T(\frac{n}{2^{k}})+(2^{k}-1)log(n) + const  -----(1)$

 

Given , $\frac{n}{2^{k}} =1$

$log n = k$

         Equation 1 become

$n+(n-1)logn - c $

Therefore it is of $O(n log(n))$

 

What is wrong with my approach

---

@Gokou: The last term which you are taking as a constant in equation (1) is not actually a constant.

It's 2x1 + 2²x2 + 2³x3 + ... + 2^k-1x(k-1)

So if you solve this series, you should get the correct answer. I remember solving this way a little while ago, see if you can solve it and post the solution, please.

Edit: I think this way of solving recurrence is not correct because we're assuming the input size to be a power of 2. We must also prove that the recurrence holds for other input sizes.

Edit2: The sum of this series would be n(lg n - 2) + 2.

Reference: https://www.youtube.com/watch?v=MLc1J6zOEvc

So T(n) = 2^k T(n/2^k) + lg n (n - 1) - [ n (lg n - 2) + 2]

Solving it you'll get T(n) =  cn - lg n - 2

---

this contradicts https://gateoverflow.in/105363/master-theorem

but why?

---

 it is not comparable with the polynomial time, nlog n  is just logn times greater than n. so, master theorem not applied for T(n)= 2T(n/2)+nlogn

---

T(n)=2T(n/2)+nlgn

according to @Arjun sir  lgn replace with root n 

T(n)=2T(n/2)+n*root n

so tc = n root n 

again we replace root n with lg 

so tc nlogn .. it is correct ??? 

@Bikram

@srestha

 

---

http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/extended_master_theorem.pdf https://math.stackexchange.com/questions/145739/prove-that-logn-o-sqrtn

---

https://gateoverflow.in/191123/t-n-sqrt-2-t-n-2-sqrt-n

 

https://cs.stackexchange.com/questions/96422/how-to-solve-tn-2t%E2%88%9Anlog-n-with-the-master-theorem

---

https://gateoverflow.in/268663/t-n-sqrt-n-t-sqrt-n-n

 

https://gateoverflow.in/46895/t-n-2t-floor-sqrt-n-log-n

Answer 2

Using Extended Master Theorem

$a=2 , b=2 , k=0 ,p= 1$ Case $1$ Follows .

Hence the Given function is $\Theta (n^{\log_2 2}) \Rightarrow \Theta (n)$

Reference : Extended Master Theorem

Using back substitution .

Comments

why  using extended form where we can directly use MT?

 

Answer 3

 T(n) = 2T(n/2) + log n
 T(1) = 1
Substitute n = 2^k

T(2^k)  = k + 2T(2^(k-1))
T(2^k)  = k + 2(k-1) + 4T(2^(k-2))
        = k + 2(k-1) + 4(K-2) + 8T(2^(k-3))
        = k + 2(k-1) + 4(K-2) + 8(k-3) + 16T(2^(k-4))
        = k + 2(k-1) + 4(K-2) + 8(k-3) + ...... + 2^kT(2^(k-k))
        = k + 2(k-1) + 4(K-2) + 8(k-3) + .......+ 2^kT(1)
        = k + 2(k-1) + 4(K-2) + 8(k-3) + .......+ 2^k  --------(1)

2T(2^k) =     2k     + 4(k-1) + 8(K-2) + ...... + 2*2^k + 2^(k+1) --------(2)

Subtracting 1 from 2, we get below
T(2^k) = - k + 2 + 4 ......    2^(k-2) + 2^(k-1) + 2^k + 2^(k+1)
           = - k + 2 * (1 + 2 + 4 + ..... 2^k)
           = -k + [2*(2^k - 1)] / [2-1]
           = -k + [2*(2^k - 1)]

T(n) = -Logn + 2*(n - 1)

T(n)  = Θ(n) 

Comments

Chatgpt was there in 2017?

---

^__^

---

Nah

Answer 4

Following is the solution of this question using Master's Method: