0
$\begingroup$

$A({n})=A(\lfloor{n/2} \rfloor)+n^2$ for $n>1$

$A({n})=1$ for $n=0,1$

Will above recursion ends in $\Theta(n^2)$ time?

1 Answers 1

3

If by "ends in $\Theta(n^2)$ time" you mean that the (naive) evaluation of $A(n)$ requires $\Theta(n^2)$ evaluations of $A$, then no. In fact, it takes only $\lfloor \log_2 n \rfloor + 1 = \Theta(\log n)$ evaluations (for $n \ge 2$).

Specifically, it's easy to show by induction on $k$ that naive evaluation of $A(n)$ takes $k$ evaluations for all $2^{k-1} \le n < 2^k$, $k \ge 2$.