TIFR CSE 2014 | Part B | Question: 11

Question

Consider the following recurrence relation:

$T\left(n\right)=
\begin{cases}
T\left(\frac{n}{k}\right)+ T\left(\frac{3n}{4}\right)+ n & \text{if } n \geq 2   \\
 1& \text{if } n=1   
\end{cases}$

Which of the following statements is FALSE?

• A. $T(n)$ is $O(n^{3/2})$ when $k=3$.
• B. $T(n)$ is $O(n \log n)$ when $k=3$.
• C. $T(n)$ is $O(n \log n)$ when $k=4$.
• D. $T(n)$ is $O(n \log n)$ when $k=5$.
• E. $T(n)$ is $O(n)$ when $k=5$.

Comments

https://gateoverflow.in/74216/%23algorithm-recurrence

---

This is one of the recurrence specific towards Akra-Bazzi method , it uses integration and I’m one of those who are below poverty line in Maths , so never bother to look for it . Hopefully these types of recurrence haven’t been asked in Gate yet :)

---

Beautiful question to understand the concept but not very beautiful to be asked in exams :P

Answer 1

Considering when $k=3$

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

Below is the recursion tree

Since, the combine work according to recurrence is linear in term of the size of the sub-problem

so at Level 1, total combine work is $n$

Combined work at level 2$=\frac{n}{3}+\frac{3n}{4}=\frac{13n}{12}$

At level 3 combine work $=\frac{n}{9}+\frac{3n}{12}+\frac{3n}{12}+\frac{9n}{16}=(\frac{13}{12})^2n$

So, at level $k$, when the recursion bottoms out at $T(1),$ the combine work will be $(\frac{13}{12})^{k-1}.n$

The left height of the tree is when the subproblem $\frac{n}{3}$ would bottom out and that is when $\frac{n}{3^k}=1$

gives $k=\log_3n$

The right height of the tree is $\log_{\frac{4}{3}}n$

for the purpose of upper bound consider right height and then sum up total combine work from root till the leaf level

$n+\frac{13}{12}n+(\frac{13}{12})^2.n+\ldots+(\frac{13}{12})^{\log_{\frac{4}{3}}n-1}n$

$=n\left [ 1+\frac{13}{12}+\ldots +(\frac{13}{12})^{\log_{\frac{4}{3}}n-1} \right ]$

$=n \left[ 1.\frac{(\frac{13}{12})^{\log_{\frac{4}{3}}n}-1}{\frac{13}{12}-1} \right]$

Using property 

$a^{\log_bc}=c^{\log_ba}$

and ignoring denominator as constant term for upper bound

$n.\left [ n^{\log_{\frac{4}{3}}\frac{13}{12}} -1\right ]=n^{1.27}$ (approximately)

Option (A) : $O(n^{1.5})$ is surely an upper bound when k=3. Correct option.

Option (B): $O(n\log n)$

this means $n.n^{0.27} \leq c.n.\log n$

$n^{0.27}\leq c.\log n$

This is clearly false as polynomials grow faster than poly-logarithms.

Option(B) can never be an upper bound, yes lower bound possible when $k=3.$

When $k=4.$

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

If we draw recursion tree for this, at every level cost comes to be n and there would be maximum $\log_{\frac{4}{3}}n$ levels

So, in this case $T(n)=O(n\log n)$. Option (C) correct.

When $k=5,$

$T(n)=T(\frac{n}{5})+T(\frac{3n}{4})+n$

It's recursion tree would look like below:

Level 1 Total cost $=n$

Level 2 total cost $=\frac{19n}{20}$

Level 3 total cost $=(\frac{19}{20})^2.n$

Level k cost $=(\frac{19}{20})^{k-1}.n$

Number of levels on right $=\log_{\frac{4}{3}}n$

Number of levels on left $=\log_5n$

For the purpose of upper bound I'll consider right height.

Computing total cost from root till leaf

$n.\left[1+\frac{19}{20}+\ldots +(\frac{19}{20})^{\log_{\frac{4}{3}}n-1} \right]$

$=n.\left[ \frac{1-(\frac{19}{20})^{\log_{\frac{4}{3}}n}}{1-\frac{19}{20}}\right]$

Ignoring denominator as we are only interested in some function of $n.$

$=n.\left[ 1-(\frac{19}{20})^{\log_{\frac{4}{3}}n} \right]$

$=n\left[1-n^{\log_{\frac{4}{3}}\frac{19}{20}} \right]$

$=n[1-n^{-0.17}]$

$=n-n^{0.82}$

So, option(E) is correct.

Option(D) which says $O(n\log n)$ might not look convincing but

$n-n^{0.82} \leq c.n\log n$

$1-\frac{1}{n^{0.17}} \leq c\log n$

for $c=1,n_o=2$ this satisfies big-oh.

Option (D) is also correct.

Answer: option(B)

Comments

Beautiful explanation brother 🤩

---

Very elaborative.

---

@Ayush Upadhyaya, Awesome explanation!! Should this be the method used in exam as it lengthy? Or it will get easier with practice?

---

@Ayush Upadhyaya

Nice answer. But, for the sake of completeness, shouldn't we consider cost at last level, where each node contribute $T(1)$ cost? 

Here the bottom level is not taken into consideration.

Ref (page 4) : https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture3.pdf 

Answer 2

Let us discuss the correct and wrong out of option A) and B) .

For that using recursion tree method , cost at 1st level = n

Cost  at  2nd level = n/3 + 3n/4 if k = 3 

                           = 13n/12  

Similarly for 3rd level we get cost = (13/12)² .n

So common ratio of G.P. = 13/12 which is > 1.

So we cannot conclude by just multiplying n with no of levels i.e. logn and hence T(n) = O(nlogn) is false in this case

So we have to find the actual GP sum as it is an increasing G.P. as cost increases each level.If we consider upper bound we have to take that branch which has larger path length and hence smaller logarithmic base will be preferred .Hence , 

no of terms that are required for G.P   =   log_4/3n

So sum of this G.P.          =  n [ (13/12)^{logn base (4/3)} - 1] / (13/12 - 1)

                                      =  12 n [n^{log(13/12)base (4/3)} - 1]

                                      =  n^1.28

                                                  =  O(n^3/2)

Hence A) option is correct and B) option is false. Let us proceed further.

If we take k = 4 , then we have cost at 2nd level = n/4 + 3n/4 = n

                        at 3rd level also we get cost     =  n

So cost remains same at each level .So here we just multiply it with the number of levels which is log_4/3n to be precise.Hence,

T(n) in this case = O(nlogn)

So option C) is true.

Now coming to option D) and E) , we have 

 cost at 1st level = n

cost at 2nd level = n/5 + 3n/4 = 19n/20

 So common ratio = 19/20 which is less than 1 hence decreasing G.P suggesting that cost is decreasing each level.

 So T(n)   =    n[1 + (19/20) + (19/20)² + .........]

               =   kn for some constant k since it is a decreasing G.P. so the inner sum result will be some constant only

               =  O(n)

               = O(nlogn) as well

Hence option both D) and E) are true.

So here B) is the only false statement here. 

Comments

thanks

---

"

For that using recursion tree method , cost at 1st level = n

Cost  at  2nd level = n/3 + 3n/4 if k = 3 

                           = 13n/12  

Similarly for 3rd level we get cost = (13/12)² .n"

can you pls explain this.??

---

I can't comprehend why ith level does work (13/12)^i * n in (1/3 --- 3/4) split and (19/20)^i * n in (1/5 --- 3/4) split. I did few experiments and it seems correct that this pattern occurs in any split. Any  good resource where I can understand this analysis.

Answer 3

We have to analyze it at three points $k = 3, 4,5.$

At  $k =4$ it is standard quick sort kind of recurrence relation. So its complexity is $O(n\times \log_4{n})$

Now if $k > 4$ then complexity will come less then $O(n\times \log_4{n})$ and vice versa for $k<4.$

So option c, d are correct but b is false.

Although partial answer is achieved but do not know how part (a) and (e) could be investigated.

Some people are taking about Akra-Bazzi method. Some ex. of this method is mentioned in following PDF.

http://www3.cs.stonybrook.edu/~rezaul/Fall-2012/CSE548/CSE548-lectures-7-8.pdf

https://math.stackexchange.com/questions/215984/solve-the-relation-tn-tn-4t3n-4n

Comments

@Arjun sir can u plz answer this q?

Answer 4

If you closely look at option C , you realize the recurrence relation is nothing but Quicksort Recurrence with 25% & 75% split of the array (and addtional +n work for partition procedure).As this comes under the average case of Quicksort . Thus it is (nlogn).Hence answer C.

Comments

Explanation is correct but answer is wrong.

---

Yeah, but the question asks for false one.

---

but in question ask about false one,

---

@Arjun sir, please mark it wrong answer.