Problem $2.$ Recurrence $($Iteration Method, $10$ points$)$

$($a$)$ Use the iteration method to give a closed form run$-$time for Heapsort's MAX$-$HEAPIFY, given

by the recurrence $T(n)=c_1+T(2\frac{n}{3}),$ where $c_1$ is a constant, with base case $T(1)=c_2.$

Solution:

$($b$)$ Give a bound on the recurrence.

Solution: