TIFR CSE 2018 | Part B | Question: 5

Question

Which of the following functions, given by there recurrence, grows the fastest asymptotically?

• A. $T(n) = 4T\left ( \frac{n}{2} \right ) + 10n$
• B. $T(n) = 8T\left ( \frac{n}{3} \right ) + 24n^{2}$
• C. $T(n) = 16T\left ( \frac{n}{4} \right ) + 10n^{2}$
• D. $T(n) = 25T\left ( \frac{n}{5} \right ) + 20\left ( n \log n \right )^{1.99}$
• E. They all are asymptotically the same

Comments

Extended Masters theorem

---

This isn't the extneded master's theorem.

This is simply the master's theorem.

---

what is Extended Master's Theorem

---

Extended Masters theorem -

If a recurrence equations looks something like this-

$T(n) = aT(n-b) + O(n^{k})$

then,

Case 1: if $a>1$, $O(n^{k}a^{n/b})$

Case 2: if $a=1$, $O(n^{k+1})$

Case 3: if $a<1$, $O(n^k)$

Answer 1

By applying master theorem,

(a) T(n) = $\Theta$($n^2$)

(b) T(n) = $\Theta$($n^2$)

(c) T(n) = $\Theta$($n^2$*log n)

(d) T(n) = $\Theta$($n^2$)

C is growing fastest.

Comments

Thanks for explanation

---

I  don't agree to @Hemant Parihar 

$(nlogn)^{1.99} = O(n^2)$ is not correct. 

Take $n=2^{256}$ 

$n^2 = (2^{256})^2 = 2^{512}$

$(nlogn)^{1.99} = (2^{256}*256)^{1.99} = (2^{264})^{1.99} = 2^{525}$

take any larger vale, hence $n^2=O(nlogn)^{1.99})$ in fact $n^2logn$ is also $O(nlogn)^{1.99})$

---

Rather than putting values consider this : 

$(nlogn)^{1.99} = n^{1.99}*(logn)^{1.99}$ and

$n^{2} = n^{1.99}*n^{0.01}$

We know that asymptotically

$n^{0.01} > (logn)^{1.99}$  [Ref: https://en.wikipedia.org/wiki/Time_complexity]

Therefore, $(nlogn)^{1.99} = O(n^2)$