Data Structures, Algorithms, & Applications in C++
Chapter 17, Exercise 5

For simplicity, assume that n = 2q for some integer q. Further, assume that k = 8. Using the substitution method, we get

t(n) = 72t(n/4) + cn2(7/4 + 1)
= 73t(n/8) + cn2((7/4)2 + 7/4 + 1)
= 74t(n/16) + cn2((7/4)3 + (7/4)2 + 7/4 + 1)
.
.
.
= 7q-3t(8) + cn2((7/4)q-4 + ... + (7/4)3 + (7/4)2 + 7/4 + 1)
= 7q-3t(8) + 4cn2((7/4)q-3 - 1)/3
= 7log2n-3t(8) + 4cn2((7/4)log2n-3 - 1)/3
= nlog27t(8)/73 + 4cn2((7/4)logn-3-1)/3
= Theta(nlog27)