Data Structures, Algorithms, & Applications in C++
Chapter 18, Exercise 9

Using the substitution method, we get

t(k) = 4t(k-1) + c
= 42t(k-2) + c(4 + 1)
= 43t(k-3) + c(42 + 4 + 1)
= 44t(k-4) + c(43 + 42 + 4 + 1)
.
.
.
= 4kt(0) + c(4k-1 + 4k-2 + ... + 4 + 1)
= 4kd + c(4k - 1)/3
= d * size2 + c(size2 - 1)/3
= Theta(size2)