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?
Asked
Active
Viewed 175 times
1 Answers
2
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.
Did
- 279,727