0
$\begingroup$

I'm trying to determine the Big-O complexity of the listed equation and want to know if my approach is valid. I tried using the Master method. It appears to be a case $3$ type problem to me, where $f(n) = \Omega (n^{\log_b a} + \epsilon)$ but there's no $\epsilon$ that will make that true.

I then tried and use an iteration method where the final iteration was $$2^kt(n/2^k)+n^3/4^{k-1}+...+n^3/4^2+n^3/4+n^3$$ where $2^k = n$

The sequence of $\frac{n^3}{4^{k-1}}$ to $n^3$ gave me a funny looking answer though when I replaced that geometric series with $$\frac{1-1/4^k}{1-1/4}$$ I believe I can replace $4^k$ with $2^k2^k$ however, which ends up giving me a final answer (the entire equation) $n+\frac{4n^3}{3}$. Is my reasoning sound, or have I made a mistake somewhere?

$\endgroup$
  • 1
    $\begingroup$ Duplicate of math.stackexchange.com/questions/25649/… ? $\endgroup$ – ً ً Jan 24 '16 at 9:35
  • $\begingroup$ Thank you, that provided a link to an answer that explained things to me a bit more. Sorry for the duplication but I couldn't find that similar question. $\endgroup$ – Greener Mar 13 '16 at 17:37
0
$\begingroup$

Using the Master Theorem, let $a=2, \, b=2, \, c= 3$. Since $\frac{\log_{2}\left(2\right)}{\log_{2}\left(2\right)}<3$ then $T(n) = \Theta(f(n))$. Therefore $T(n) = \Theta(n^3)$. enter image description here

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is an interesting way of looking at the problem that I wasn't familiar with. Thanks for the answer. $\endgroup$ – Greener Mar 13 '16 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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