Using recursion tree to find time complexity of $T(n)=T(n/7)+T(3n/4)+cn$, where $c$ is a constant

286 Views Asked by At

After drawing the recursion tree,the longest path can be found,which is $1\to 3n/4\to\cdots\to(3n/4)^k$. So the length is $\log_{4/3} n+1$. Thus $T(n)\le cn[1+25/28+...+(25/28)^{\log_{4/3} n+1}]$. That is $\frac{28cn}{3}[1-(25/28)^{\log_{4/3} n+1}]$. So $T(n)=O(n)$. Is this correct?