0
$\begingroup$

The big-O bound seems largely governed by how many times we can take the input $n$ by the $\frac{2}{3}$ power until it reaches some constant like 1.

How do I start formalizing this problem in math terms?

$\endgroup$
2
$\begingroup$

Hint: Let $a=\frac32$. First find a recursion for $$U(k)=T(\exp(a^k)),$$ then deduce a formula for $U(k)$, finally determine for which $k$, $$\exp(a^k)\approx n, $$ when $n$ is large.

| cite | improve this answer | |
$\endgroup$

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.