Recurrence Part II

Determining Recursion Levels

Now let’s take an example of how we get to the base case, starting with an array of size 8. We’ll first divide it into half, creating two arrays of size 4. Next, we’ll split each of the two arrays of size 4 into two arrays of size 2. Now we have four arrays of size 2 but we haven’t hit the recursion’s base case, so we’ll split each of the four arrays of size 2 into a single array of size 1. When we finally hit the recursion’s base case, we will have eight arrays of a single element.

Note, we need to find the number of levels or recursions it took to break the problem of size 8 into a problem of size 1. At each recursion level, we divide the problem by 2. So we may ask, how many times do we need to divide the input size by 2 to get to a problem of size 1?. For 8 we know we need to divide thrice by 2 to get to a problem size of 1. In other words, we can ask, 2 raised to what power would yield 8?

$$2^x = 8$$

The above equation is in exponential form and can be expressed in logarithmic form as follows:

$$\log_2(8) = x$$

$$\log_2(8) = 3$$

Note in our case, the number of recursion levels is log$_{2}$n+1. We need to add 1 for the root level. Knowing the number of recursion levels a given input results in, we can determine the running time of the algorithm by multiplying the number of recursion levels with the cost incurred at each level. The illustration below shows the recursion levels and the total cost at each level, where n is the input size and d is the cost to divide the problem into two subproblems.