Exercise 2: Applying the Master Theorem to T(n) = T(n/2) + n^2 — Possible Solution
====================================================================================

GIVEN
------------------------------
T(n) = T(n/2) + n^2

STEP 1: IDENTIFYING a, b, AND f(n)
------------------------------
a = 1 (one recursive call)
b = 2 (each call works on half the input)
f(n) = n^2 (the non-recursive work per call)

STEP 2: COMPUTING n^(log_b a)
------------------------------
log_b(a) = log base 2 of 1 = 0

n^(log_b a) = n^0 = 1

STEP 3: COMPARING f(n) TO n^(log_b a)
------------------------------
f(n) = n^2
n^(log_b a) = 1 (i.e., n^0)

n^2 grows dramatically faster than n^0 = 1 as n increases - f(n) is
the clear winner here.

STEP 4: IDENTIFYING THE CASE AND THE RESULT
------------------------------
Since f(n) grows faster than n^(log_b a), per this chapter's own
Master Theorem table this is CASE 3 - the non-recursive work
dominates the recursion entirely.

  T(n) = Theta(f(n)) = Theta(n^2)

WHY THIS WORKS AS AN ANSWER
------------------------------
Each of a, b, and f(n) is identified directly from the given
recurrence, n^(log_b a) is computed explicitly rather than estimated,
and the case is selected by directly comparing the two functions'
growth rates per this chapter's own three-case table, rather than
guessing the answer from the recurrence's overall shape.