Return to Answer

As $T$ is clearly non-decreasing, it is sufficient to consider $n=2^k$ for asymptotic growth. In this case, the recurrence simplifies to

As $T$ is clearly non-decreasing, it is sufficient to consider $n=2^k$ for asymptotic growth. In this case, the recurrence simplifies to

$\qquad \begin{align}T(0) = T(1) &= 0 \\ T(n) &\leq T\left(\left\lceil\frac{n}{2}\right\rceil\right) + T\left(\left\lceil\frac{n}{2}\right\rfloor\right) + 7n\end{align}$

As $T$ is clearly non-decreasing, it is sufficient to consider $n=2^k$ for asymptotic growth. In this case, the recurrence simplifies to

$\qquad \begin{align}T(0) = T(1) &= 0 \\ T(n) &\leq T\left(\left\lceil\frac{n}{2}\right\rceil\right) + T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + 7n\end{align}$

As $T$ is clearly non-decreasing, it is sufficient to consider $n=2^k$ for asymptotic growth. In this case, the recurrence simplifies to

This already includes proofs of well-definedness and termination. Find an (almost) complete correctness proof here.

This already includes proofs of well-definedness and termination. Find an (almost) complete correctness proof here.