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

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: