Big-O complexity of $2t(\frac{n}{2}) + n^3$

108 Views Asked by At

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?

1

There are 1 best solutions below

1
On BEST ANSWER

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