retagged by
23,456 views
24 votes
24 votes

Consider the following recurrence relation.

$$T\left ( n \right )=\left\{\begin{array}  {lcl} T(n ∕ 2)+T(2n∕5)+7n & \text{if} \; n>0\\1 & \text{if}\; n=0 \end{array}\right.$$

Which one of the following options is correct?

  1. $T(n)=\Theta (n^{5/2})$
  2. $T(n)=\Theta (n\log n)$
  3. $T(n)=\Theta (n)$
  4. $T(n)=\Theta ((\log n)^{5/2})$
retagged by

7 Answers

Best answer
48 votes
48 votes

Correct Option: C


At first, draw two levels of the recursion tree:

Size of the problem will reduce as we go down a level each time in the tree.

Hence, in this case root will be the dominant part. 

Final ans is  $T(n) = \Theta (n)$     (order of the root)   (you have to ans in less than $30$ sec!)

$\text{Let}\; f(n) = 1 + a + a^2 + \ldots  + a^n, a<1 \\ \quad \implies f(n) =  \frac{1 – a^{(n+1)}}{1-a}$

When $n \to \infty, f(n) = \frac{1}{1-a} = O(1)$ since $c = \frac{1}{1-a} $ is a constant.

We can see that the size of problem reduces geometrically, and root is the dominating part.

Note: Apply the following method for divide and conquer recursions because the size of the problem reduces geometrically. Not for subtract and conquer where it might reduce arithmetically!

And to apply this idea, all the conditions of Master theorem must be satisfied.


Everything given below is not required for GATE, it's just to explain the idea.

$T(n) =  aT\left(\frac{n}{b} \right) + \Theta(n^k) \; ,  n>1$

$T(1) = c $

$($Assume all conditions of the Master theorem to be true here, $b>1).$

Let height of this tree be $h,$

$ \frac{n}{b^h} = 1 \implies  b^h = n \implies  h = \log_b(n) $

No. of leaves $= \underbrace{a*a*a*\ldots * a}_{\text{times the height of the tree}}= a^{\log_b(n)} = n^{\log_b(a)}$

Here’s the relation with master theorem:

Case 1 (root is dominant): $cn^k > ac\left(\frac{n}{b}\right)^k $

$ \implies 1 > \frac{a}{b^k} \implies  b^k > a \implies \boldsymbol{k > \log_b(a)}$

$\implies n^k > n^{\log_b(a)}$

This case of Master theorem says $T(n) = \Theta (n^k)$, which is nothing but the order of root. 

(We are kinda deriving cases of the master theorem using intuition)

Case 2 (root is equal to all levels):  $cn^k = ac\left(\frac{n}{b}\right)^k $

$  \implies 1 = \frac{a}{b^k} \implies b^k = a \implies  \boldsymbol{k = \log_b(a)}$

$\implies n^k = n^{\log_b(a)}$

According to the Master theorem, $T(n) = \Theta (n^k \log(n))$.

All the levels are equally dominant, hence final result will be the sum of all levels. That is,

size of a particular level $\times$ the height  $\implies n^k\times\log_b(n)$, Hence $T(n) = \Theta (n^k \log_b(n))$.

Case 3 (leaf level is dominant): 

$\implies 1 <\frac{a}{b^k} \implies b^k < a \implies \boldsymbol{k < \log_b(a)}$

$\implies n^k < n^{\log_b(a)}$

According to Master theorem, $T(n) = \Theta (n^{\log_b(a)})$

As the leaves’ levels are dominant, Ans will be in the order of the leaf’s level = Order of no of leaves in the tree (because base condition will be a constant)

Hence $T(n) =\Theta (n^{\log_b(a)})$

After reading this logic you’ll never have to remember the Master theorem!

Reference


You’ll find different kind of recurrence relations and how to solve them here:

edited by
45 votes
45 votes

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

$\text{Recursion Tree would look like :}$

Since, $\frac{n}{2}> \frac{2n}{5}$, So, the height of the rightmost subtree will determine the lower bound of the given recurrence, and the height of the leftmost subtree will determine the upper bound of the given recurrence.

Height of the leftmost subtree is : $\log_2 n$ and so,

$T(n) \leq 7n + 7 \left( \frac{9}{10} \right)n + 7 \left( \frac{9}{10} \right)^2n + \ldots +7 \left( \frac{9}{10} \right)^{\log_2n}n$

$\implies T(n) \leq 7n \left(1+ \frac{9}{10} + \left (\frac{9}{10}\right)^2 + \ldots + \left(\frac{9}{10} \right)^{\log_2n }\right)$

$\implies T(n) \leq 7n \left (\frac{1- (\frac{9}{10})^{\log_2n + 1}}{1 – \frac{9}{10}} \right) = 70n \left(1 – (\frac{9}{10})^{\log_2n +1} \right)$

$ \quad = 70n – 70n \left(n^{\log_2\frac{9}{10}}\frac{9}{10} \right)  = 70n – 63n^{0.85}$

$\implies T(n) \leq 70n$

$\implies T(n)\in O(n)$

Height of the rightmost subtree is $: \log_{5/2} n$ and so,

$T(n) \geq 7n + 7 \left( \frac{9}{10} \right)n + 7 \left( \frac{9}{10} \right)^2n + \ldots +7 \left( \frac{9}{10} \right)^{\log_{5/2}n}n$

$\implies T(n) \geq 7n \left(1+ \frac{9}{10} + \left(\frac{9}{10} \right)^2 + \dots + \left(\frac{9}{10} \right)^{\log_{5/2}} n \right)$

$\implies T(n) \geq 7n \left(\frac{1- \left(\frac{9}{10}\right)^{\log_{5/2} (n + 1)}}{1 – \frac{9}{10}} \right) = 70n \left(1 – (\frac{9}{10})^{\log_{5/2}n + 1} \right)$

$ \qquad = 70n – 70n \left(n^{\log_{5/2}\frac{9}{10}}\frac{9}{10}\right) = 70n – 63n^{0.89}$

$\implies T(n) \geq n \left(70 – \frac{63}{n^{0.11}}\right )$

$\because \displaystyle{} \lim_{n \rightarrow\infty }\frac{63}{n^{0.11}} = 0$ for n $\geq 1$ So, $\left(70 – \frac{63}{n^{0.11}}\right )$ is a positive constant $c >0$ for large $n$ and so, $T(n) \geq cn.$

  • $T(n)\in \Omega(n)$
  • $T(n) \sim 70n$
  • $T(n) \in \Theta(n)$

 

Edit: For lower bound,

$T(n) \geq 7n + 7 \left( \frac{9}{10} \right)n + 7 \left( \frac{9}{10} \right)^2n + \ldots +7 \left( \frac{9}{10} \right)^{\log_{5/2}n}n$

which implies $T(n) \geq 7n $

So, $T(n) \in \Omega(n)$ for sufficiently large $n.$

edited by
5 votes
5 votes

O(n)

Please correct me if I am wrong

Basic recurrence tree method helps in this

I would say this question is easy concept wise, but time consuming

 

edited by
Answer:

Related questions

18 votes
18 votes
3 answers
4
Arjun asked Feb 18, 2021
11,519 views
A binary search tree $T$ contains $n$ distinct elements. What is the time complexity of picking an element in $T$ that is smaller than the maximum element in $T$?$\Theta(...