
1130 CHAPTER 15 Running Time Analysis
Let’s compute the running time of powerOf2A as a function of the input n;
we will call it T1(n).
In the base case (n is equal to 0), powerOf2A makes only one comparison
and returns 1. Thus,
T1(0) = 1
Generally, since it takes T1(n) to compute and return powerOf2A(n), then
it takes T1(n – 1) to compute and return powerOf2A(n – 1).
Thus, in the general case, the comparison in the if statement will cost us
1 instruction; computing and returning powerOf2A(n – 1) will cost us
T1(n – 1); and multiplying that result by 2 will cost us 1 instruction. Thus,
the total time T1(n) can be expressed as follows:
T1(n) = 1 + T1(n