2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – Raphael
    Sep 16, 2018 at 11:00
  • $\begingroup$ Note also our reference question, and the many questions about recurrence-relation. $\endgroup$
    – Raphael
    Sep 16, 2018 at 11:01
  • $\begingroup$ Please read about master's theorem $\endgroup$ Sep 16, 2018 at 12:17
  • $\begingroup$ @HUDATARIQL1F11BSCS2330 You keep writing "underroot" -- what do you mean by that? It's not a standard mathematical term. $\endgroup$ Sep 16, 2018 at 13:57
  • 1
    $\begingroup$ Possible duplicate of Solving or approximating recurrence relations for sequences of numbers $\endgroup$ Sep 16, 2018 at 13:57

2 Answers 2

1
$\begingroup$

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})$.

$\endgroup$
1
$\begingroup$

\begin{equation} 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}} \end{equation} On the $k^{th}$ iteration, we get \begin{equation} T(n) = 4^kT(\frac{n}{2^k}) + \sum\limits_{i=0}^{k-1} 4^i (\frac{n}{2^i})^{\frac{5}{2}} \end{equation} 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 \begin{equation} \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}}})} \end{equation} where the last equality comes from realizing that we have a geometric series. Notice that \begin{equation} \frac{4}{2^{\frac{5}{2}}} = (\sqrt{2})^{-1} \end{equation} So \begin{equation} \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}} \end{equation} But algorithm terminates at $k = \log_2 n$ so \begin{equation} \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) \end{equation} where $\alpha = \frac{1}{1- \frac{\sqrt{2}}{2}}$ But \begin{equation} (\sqrt{2})^{-\log_2 n} = \frac{1}{(\sqrt{2})^{\log_2 n}} = \frac{1}{2^{\log_2 \sqrt{n}}} = \frac{1}{\sqrt{n}} \end{equation} So \begin{equation} \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}}) \end{equation} So \begin{equation} 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}}) \end{equation}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.