Solving recurrence relations using geometric series

Geometric series: A fundamental concept#

To understand how geometric series can simplify recurrence analysis, we first have to understand the concept of the geometric series. A geometric series is a sequence of numbers in which each term after the first is found by multiplying the previous term by a fixed, nonzero number called the common ratio. The formula for the sum of a geometric series is as follows:

$$\begin{align} \nonumber S_n &= ar^0 + ar^1 + ar^2 + ar^3 + \ldots + ar^{n-2} + ar^{n-1}. \\ \nonumber &= ar^{n-1} + ar^{n-2} \ldots + ar^3 + ar^2 + ar^1 +ar^0. \\ \end{align}$$

The two series above have a closed summation captured by the following formula:

$$\begin{align} \boxed{S_n = \frac{a(1-r^n)}{1-r}.} \end{align}$$

where,

• $S_n$ is the sum of the series with n terms.
• $a$ is the first term.
• $r$ is the common ratio.
• $n$ is the number of terms.

There are two key insights from the geometric series formula:

1. Increasing geometric series: An increasing geometric series is bounded by the last term.
2. Decreasing geometric series: A decreasing geometric series is bounded by the first term.

You’re encouraged to look at the proofs of these two properties. These two properties form the basis of our new approach to solving recurrences.

Before we go into the details of solving recurrences, let’s look at some example series and establish bounds for the series using the two properties mentioned above.

Examples: Sum of the series with a specific common ratio rrr#

Let’s look at the following example:

$$\begin{align} \nonumber S_1 &= T + T / 2 + T/4 + \ldots + 8 + 4 + 2 + 1. \\ \nonumber S_2 &= 1+2+4+8+\ldots + T/4 + T/2 + T. \\ \end{align}$$

• $S_1$ is an example of a decreasing geometric series where $T$ is any value bigger then $1$, with a common ratio of $\frac{1}{2}$, and it’s bounded by $O(T)$.

• Similarly, $S_2$ is an example of an increasing geometric series with a common ratio of ${2}$, and it’s bounded by $O(T)$.

Let’s explore some further examples.

Example: Let’s explore the following example and see if it’s bound using the geometric series facts presented above.

$$S(n) = 1+2+4+8+16+...+n+2 \times n + 4 \times n + ... + n\times n.$$

This is an increasing geometric series that’s bounded by the last term, i.e., $S(n) \approx O(n^2)$.

If we open the recurrence above mathematically, it will be something like this (for reference, look at the recurrence tree above):

$$\begin{align} \nonumber T(n) &= 4 T(n/2) + O(1), \\ \nonumber &= 4 ( 4 T(n/4) + 1 ) + O(1), \\ \nonumber &= 4 ( 4 (4 T(n/8) + 1) + 1 ) + 1, \\ \nonumber &= 4(4(4(...(1))...+1)+1)+1, \\ &= 4^{levels} + 4^{levels-1} + 4^{levels-2} + ... + 4^3 + 4^2 + 4 + 1. \\ \end{align}$$

If we rewrite the last equation in increasing level order, i.e., level 1’s cost first, then the second, then the third, and so on, then the rearranged equation will be as follow:

$$\begin{align} T(n) &= 1 + 4 + 4^2 + 4^3 + ... + 4^{levels-2} + 4^{levels-1} + 4^{levels}. \\ \end{align}$$

This last equation clearly depicts an increasing geometric series that is bounded by the last term. This results in the asymptotic complexity of $O(4^{levels})$.

Calculation for the number of levels#

As we go down the recursion tree, the size of $n$ decreases by the common ratio of $\frac{1}{2}$ therefore, the total number of levels can be seen as the size of the sequence:

$$n, \frac{n}{2}, \frac{n}{4}, \frac{n}{8}, \ldots, \frac{n}{2^k}\approx 1.$$

Here $k$ is the number of levels, which can be calculated by solving for $k$ for the last term (which is 1, the base case):

$$\frac{n}{2^k} = 1 \implies n = 2^k \implies \log_2 n = log_2 2^k.$$

$$k = log_2 n.$$

Therefore, the number of levels is equal to $\log_2 n$. So,

$$4^{levels} \implies 4^{\log_2 n} \implies n^{\log_2 4} = n^2 \space \space \space \space \because (a^{\log_b c} = c^{\log_b a}).$$

Therefore, the asymptotic complexity of the recurrence is $O(n^2)$.

In general#

In case the recurrence yields an increasing geometric series, the recurrence will be bounded above the last level, i.e.,

$$T(n) = a T(n/b) + n^c.$$

$T(n)$ will be bounded by $O(a^{\log_b n}) \implies O(n^{log_b a})$.

Note: It’s interesting that the cost equals the number of nodes at the last level.

If we open the recurrence above mathematically, it will be something like this (for reference, look at the recurrence tree above):

$$\begin{align} \nonumber T(n) &= 2 T(n/2) + n^2 \\ \nonumber &= 2 ( 2 T(n/4) + (\frac{n}{2})^2 ) + n^2 \\ \nonumber &= 2 ( 2 (2 T(n/8) + (\frac{n}{4})^2) + (\frac{n}{2})^2 ) + n^2 \\ \nonumber &= 2(2(2(...(1))...+(\frac{n}{4})^2)+(\frac{n}{2})^2)+n^2 \\ &= 2^{levels} + 2^{levels-1} + 2^{levels-2} + ... + \frac{n^2}{8} + \frac{n^2}{4} + \frac{n^2}{2} + n^2. \\ \end{align}$$

Calculation for the number of levels#

As we go down the recursion tree, the size of $n$ decreases by a factor of $2$. Therefore, the total number of levels is equal to $\log_2 n$. Therefore,

$$2^{levels} \implies 2^{\log_2 n} \implies n^{\log_2 2} = n \space \space \space \space \because (a^{\log_b c} = c^{\log_b a}).$$

If we rewrite the last equation in increasing level order, i.e., level 1’s cost first, then the 2nd, then the third, and so on, then the rearranged equation will be:

$$n^2 + \frac{n^2}{2} + \frac{n^2}{4} + \frac{n^2}{8} + ... + 2n + n.$$

This is just a decreasing geometric series ending on $n$, Therefore, the total bound will be $O(n^2)$, bounded by the first term.

If we open the recurrence above mathematically, it will be something like this (for reference, look at the recurrence tree above):

$$\begin{align} \nonumber T(n) &= 3T(n/3) + n \\ \nonumber &= 3 ( 3T(n/9) + n/3 ) + n \\ \nonumber &= 3 ( 3(3 T(n/27) + n/9) + n/3 ) + n \\ \nonumber &= 3(3(3(...(1))...+n/9)+n/3)+n \\ &= 3^{levels} + 3 \times 3^{levels-1} + 3^2 \times 3^{levels-2} + ... + 27\times \frac{n}{27} + 9\times \frac{n}{9} + 3\times \frac{n}{3} + n \times 1. \\ \end{align}$$

If we rearrange the last equation such that level 1 is the first, level 2 is the second, and so on, the equation becomes:

$$\begin{align} \nonumber T(n) &= n\times 1 + 3\times \frac{n}{3} + 9\times \frac{n}{9} +\cdots + 3^2 \times 3^{levels-2} + 3 \times 3^{levels-1} + 1\times 3^{levels}. \end{align}$$

$$\boxed{ \begin{align} \nonumber T(n) &= n+n+n+\cdots+n.\end{align}}$$

Calculation for the number of levels#

As we go down the recursion tree, the size of $n$ decreases by a factor of $3$. Therefore, the total number of levels is equal to $\log_3 n$. So, because every term in the series equation above is $n$ and there are $O(\log n)$ levels, the total time complexity bound will be $O(n \log n)$.

It’s important to remember the following property:

Logarithm’s base disappears in Big O notation#

The logarithm function has an interesting property that, makes the base of the $\log$ disappear in Big O notation:

$$\log_c n = \frac{\log_b n}{\log_b c}.$$

Notice, in the above equation that, $\log_b c$ is always just a constant. Therefore, in Big O notation:

$$\log_c n = \frac{\log_b n}{constant} \implies O(\log_c n) \approx O(\log_b n).$$

This is the reason why computer scientists seldom write the base of the logarithm.