Exercise 1: Verifying T(n) = 4T(n/2) + n at n=8 — Possible Solution
====================================================================

GIVEN
------------------------------
T(n) = 4T(n/2) + n, T(1) = 1

STEP 1: UNROLLING STEP BY STEP
------------------------------
T(1) = 1
T(2) = 4T(1) + 2 = 4(1) + 2 = 6
T(4) = 4T(2) + 4 = 4(6) + 4 = 28
T(8) = 4T(4) + 8 = 4(28) + 8 = 120

So T(8) = 120, confirmed by direct substitution.

STEP 2: COMPARING TO THE MASTER THEOREM PREDICTION
------------------------------
This chapter's own Master Theorem analysis classified this recurrence
as Case 1, predicting T(n) = Theta(n^2). At n=8: n^2 = 64.

T(8) = 120, and 120 / 64 = 1.875

This ratio is NOT expected to equal exactly 1 - Theta notation only
guarantees the ratio settles toward SOME constant as n grows, not
that the constant is 1. Per this chapter's own finding-box, computing
this same ratio at larger values of n (16, 32, 64) shows it steadily
converging toward approximately 2, confirming T(n) genuinely is
Theta(n^2) even though the raw numbers (120 vs. 64) don't match one-
to-one at this particular small n.

WHY THIS WORKS AS AN ANSWER
------------------------------
T(8) is computed by direct step-by-step substitution rather than
trusting the Master Theorem's prediction blindly, and the comparison
to n^2 is interpreted correctly using this chapter's own explanation
that Theta notation predicts a converging RATIO, not an exact numeric
match at any single small value of n.