Exercise 2: The Recurrence for a Three-Way Divide-and-Conquer Function — Possible Solution
====================================================================================

GIVEN
------------------------------
A function makes 3 recursive calls, each on a third (n/3) of the
original input, plus O(n) work to combine the results.

WRITING THE RECURRENCE
------------------------------
Following this chapter's own general recurrence shape, and directly
mirroring the structure of this chapter's own merge sort example (2
calls on halves plus O(n) combining work, giving T(n) = 2T(n/2) +
O(n)):

  T(n) = 3T(n/3) + O(n)

This states: the total cost at input size n equals the cost of 3
separate recursive calls, each working on a subproblem one-third the
size of the original, plus a linear amount of extra work to combine
their results back together.

WHY THIS WORKS AS AN ANSWER
------------------------------
The recurrence is constructed by directly translating the two given
pieces of information - the number and size of the recursive calls
(3 calls, each on n/3), and the non-recursive combining work (O(n)) -
into this chapter's own general recurrence template, following the
exact same pattern demonstrated in the chapter's own merge sort
example rather than inventing a new structure. Per this chapter's own
forward reference, actually SOLVING this recurrence (rather than just
writing it) is Chapter 6's own Master Theorem territory.