Overall Complexity for $A(n)=2A(n/3)+2$ - Can't figure out effect of "d" for Master Theorem

20 Views Asked by At

Based on the Master Theorem, the values are:

$A = 2$ $B = 3$ $D = 0$

Therefore, $2 > 3^0$

Based on the Master Theorem, the answer should be

$O(n^0)$, but on my quiz this isn't the answer.

How should I consider this equation if "d" for the Master Theorem isn't "apparent"?

1

There are 1 best solutions below

0
On BEST ANSWER

$c_{crit} = \log_3 2$ and $f(n) \in O(n^0)$ with $0 < c_{crit}$ or as you say $3^0 < 3^{\log_3 2} = 2$. This means that we are in case 1 of the master theorem. $\Theta (n^{c_{crit}})$. You put $c$ instead of $c_{crit}$.