Java Illuminated, 5th Edition

15.3 Running Time Analysis of Algorithms and Impact of Coding: Evaluating Recursive Methods

In this section, we will learn how to compute the running time of a recursive method. We will also look at how coding a method has a direct impact on its running time.

Consider coding a recursive method that takes one parameter, n, and returns 2ⁿ. There are several ways to code that method, and we will consider two of them here so that we can assess which algorithm is more efficient.

Our first method, powerOf2A, is designed using this approach:

• when n = 0, 2⁰ = 1. This is our base case.

• For our general case, we use this calculation: 2ⁿ = 2 * 2^{n – 1}

This first problem formulation results in the method shown in Example 15.4.

EXAMPLE 15.4 First Recursive ...