Mathematical Foundation of Computer Science

DHARM

RECURRENCE RELATIONS WITH CONSTANT COEFFICIENTS 73

Example 3.9. Solve the following recurrence

1. T(n) = 8 T(n/2) + n^2 for n = 2 and n is a power of 2


2. T(n) = 2 T(n/2) + n for n = 2 and n is a power of 2


3. T(n) = 64 T(n/4) + n^6 for n = 4 and n is a power of 4


4. T(n) = 2 T(n/2) + cn log n for n = 2 and n is a power of 2
   In each case assume T(1) = constant.
   Sol. We can solve above recurrences by any of the method discussed above. We attempt the
   solution of the recurences using both methods, first by master theorem and later by substitu-
   tion method.

Master Theorem

1. For the recurrence T(n) = 8 T(n/2) + n^2 ; we have a = 3, b = 8 and f(n) = n^2. Determine
   n logba = n log^2 θ = θ(n^3 ). Since f(n) = O(n log^2 θ−∈), where ∈ = 1 (case 1 of theorem 3.2) that
   return the solution T(n) = θ(n log^2 θ) = θ(n^3 ).


2. For the recurrence T(n) = 2 T(n/2) + n ; we have a = 2, b = 2 and f(n) = n, thus n logba =
   n log^22 = n. Since f(n) = θ(n log^22 ) = θ(n) (apply case 2 of theorem 3.2). Therefore, the
   solution of the recurrence is T(n) = θ(n log^22 log n) = θ(n log n).


3. In the recurrence T(n) = 64 T(n/4) + n^6 ; we have a = 64, b = 4, and f(n) = n^6 and so n logba
   = n log^464 = n^3. Since f(n) = Ω(n log^464 +∈), where ∈ = 3 (case 3 of the theorem 3.2). Hence,
   the solution T(n) = θ(f(n)) = θ(n^6 ).


4. Recurrence T(n) = 2 T(n/2) + cn log n; can not solved through master theorem. Since, f(n)
   = cn log n is asymptotically dominant than n logba = n, but not polynomially dominant.
   So, no case will determine the solution of this recurrence.
   Substitution Method


5. In the recurrence T(n) = 8 T(n/2) + n^2 ; a = 8, b = 2 and f(n) = n^2. Thus, n logba = n^3 and h(n)
   = f(n)/ n logba = n^2 /n^3 = n–1 = O(nk) where k = – 1 < 0. Therefore, g(n) = O(1).(from the table
   Fig. 3.4). Hence the solution is
   T(n) = n^3 [T(1) + O(1)] = θ(n^3 ).


6. Recurrence T(n) = 2 T(n/2) + n ; we obtain n logba = n log^22 = n and h(n) = n/n = 1= θ((log n)^0 ).
   From Fig. 3.4 we obtain corresponding g(n) = θ(log n), hence, solution is
   T(n) = n[T(1) + θ(log n)] = θ(n log n).


7. For the recurrence T(n) = 64 T(n/4) + n^6 ; we obtain h(n) = n^6 / n log^464 = n^3 = Ω(nk) where
   k = 3 > 0. From the table we find corresponding g(n) = θ(h(n)) = θ(n^3 ). Hence the solution
   T(n) = n log^464 [T(1) + θ(n^3 )] = θ(n^6 ).


8. Unsolved recurrence T(n) = 2 T(n/2) + cn log n ; can be solved using substitution method.
   We obtain h(n) = cn log n/n log^22 = c log n = c θ((log n)^1 ). The corresponding g(n) will be
   cθ((log n)^2 /2). Hence the solution
   T(n) = n [T(1) + c θ((log n)^2 /2)] = θ(n log^2 n).