# Not able to find any pattern for $4T(n/2)+n^2 n^{1/2}$

I have tried my best but I'm not able to find any pattern for the $n^2n^{1/2}$ part. This question must be solved iteratively and I get totally clueless after two iteration.s I've to find tight bound in big-O.

• Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat?
– Raphael
Sep 16, 2018 at 11:00
• Note also our reference question, and the many questions about recurrence-relation.
– Raphael
Sep 16, 2018 at 11:01
Here is what happens when you expand the recurrence: \begin{align*} T(n) &= n^{5/2} + 4(n/2)^{5/2} + 4^2(n/2^2)^{5/2} + 4^3(n/2^3)^{5/2} + \cdots \\ &= n^{5/2} \left(1 + \frac{4}{2^{5/2}} + \left(\frac{4}{2^{5/2}}\right)^2 + \left(\frac{4}{2^{5/2}}\right)^3 + \cdots \right). \end{align*} Since $4/2^{5/2} = 1/\sqrt{2} < 1$, the large bracketed expression converges, and so the answer is $T(n) = \Theta(n^{5/2})$.
$$T(n) = 4T(\frac{n}{2}) + n^{\frac{5}{2}} = 4^2T(\frac{n}{2^2}) + 4(\frac{n}{2})^{\frac{5}{2}} + n^{\frac{5}{2}}$$ On the $k^{th}$ iteration, we get $$T(n) = 4^kT(\frac{n}{2^k}) + \sum\limits_{i=0}^{k-1} 4^i (\frac{n}{2^i})^{\frac{5}{2}}$$ which terminantes at $k = \log_2 n$ The part $$4^kT(\frac{n}{2^k}) = O(4^{\log_2 n}) = O(n^2)$$ The sum part could be arranged as $$\sum\limits_{i=0}^{k-1} 4^i (\frac{n}{2^i})^{\frac{5}{2}} = n^{\frac{5}{2}} \sum\limits_{i=0}^{k-1} 4^i (\frac{1}{2^i})^{\frac{5}{2}} = n^{\frac{5}{2}} \sum\limits_{i=0}^{k-1} \Big( \frac{4}{2^{\frac{5}{2}}} \Big)^{i} = n^{\frac{5}{2}} \frac{1- \big(\frac{4}{2^{\frac{5}{2}}}\big)^k}{1 - (\frac{4}{2^{\frac{5}{2}}})}$$ where the last equality comes from realizing that we have a geometric series. Notice that $$\frac{4}{2^{\frac{5}{2}}} = (\sqrt{2})^{-1}$$ So $$\sum\limits_{i=0}^{k-1} 4^i (\frac{n}{2^i})^{\frac{5}{2}} = n^{\frac{5}{2}} \frac{1 - (\sqrt{2})^{-k}}{1 - \frac{\sqrt{2}}{2}}$$ But algorithm terminates at $k = \log_2 n$ so $$\sum\limits_{i=0}^{k-1} 4^i (\frac{n}{2^i})^{\frac{5}{2}} = O( n^{\frac{5}{2}} \frac{1 - (\sqrt{2})^{-\log_2 n}}{1 - \frac{\sqrt{2}}{2}} ) = O\Big( \alpha n^{\frac{5}{2}} (1 - (\sqrt{2})^{-\log_2 n}) \Big)$$ where $\alpha = \frac{1}{1- \frac{\sqrt{2}}{2}}$ But $$(\sqrt{2})^{-\log_2 n} = \frac{1}{(\sqrt{2})^{\log_2 n}} = \frac{1}{2^{\log_2 \sqrt{n}}} = \frac{1}{\sqrt{n}}$$ So $$\sum\limits_{i=0}^{k-1} 4^i (\frac{n}{2^i})^{\frac{5}{2}} = O( n^{\frac{5}{2}} \frac{1 - (\sqrt{2})^{-\log_2 n}}{1 - \frac{\sqrt{2}}{2}} ) = O\Big( \alpha n^{\frac{5}{2}} (1 - \frac{1}{\sqrt{n}}) \Big) = O( n^{\frac{5}{2}})$$ So $$T(n) = \underbrace{4^kT(\frac{n}{2^k})}_{O(n^2)} + \underbrace{\sum\limits_{i=0}^{k-1} 4^i (\frac{n}{2^i})^{\frac{5}{2}}}_{ O( n^{\frac{5}{2}})} = O( n^{\frac{5}{2}})$$