How does my textbook solve this summation equation for the answer?

Question

Summations have always been my weakness in mathematics, and it's showing here as I'm very confused how my textbook, Introduction to Algorithms, goes from basically the second half of the following picture, to saying it's O($n^2$). I included the top half in case more information was helpful.

Can anyone explain to me (as clearly as possible, I really am poor at summations) how to get to the bottom of that equation from the summation? I'd greatly appreciate it.

Answer 1

I'm assuming you're talking about the step from the summation to the fraction.

The sum $$\sum_{i=0}^\infty \left(\frac 3 {16}\right)^i$$ is a geometric series with $r=\frac 3{16}$ and $a=1$. The sum of a geometric series is $$\sum=\frac a {1-r}$$so the sum of this series is $\frac 1 {1-\frac 3{16}}$.

As for the other steps:

• The step from (1) to (2) is true because all terms of the summation will be positive, so the sum of $n$ terms is always less than the sum of $\infty$ terms.
• The step from (2) to (3) is outlined above.
• The step from (3) to (4) is a simple evaluation of the fractional quantity.
• The step from (4) to (5) is true because $\frac {16}{13}c$ is a constant, and $O$-notation allows you to remove constants. Also, $n^{{\log_4}{3}} < n^2$ so we discard the smaller quantity.

Answer 2

In the summation $$\sum_{i=0}^{\log_4n-1}\left(\frac3{16}\right)^icn^2$$ the factor $cn^2$ is a constant with respect to $i$, the index of summation, so we can pull it out:

$$\sum_{i=0}^{\log_4n-1}\left(\frac3{16}\right)^icn^2=cn^2\sum_{i=0}^{\log_4n-1}\left(\frac3{16}\right)^i\;.$$

Now extend that last summation: the terms involved are all positive, so

$$\sum_{i=0}^{\log_4n-1}\left(\frac3{16}\right)^i<\sum_{i=0}^\infty\left(\frac3{16}\right)^i\;.$$

That last summation is a geometric series with ratio $\frac3{16}$, and since the absolute value of this ratio is less than $1$, we can apply the standard summation formula:

$$\sum_{i=0}^\infty\left(\frac3{16}\right)^i=\frac1{1-\frac3{16}}=\frac{16}{13}\;.$$

Thus,

$$\sum_{i=0}^{\log_4n-1}\left(\frac3{16}\right)^icn^2<\frac{16}{13}cn^2\;.\tag{1}$$

Since $\frac{16}{13}c$ is constant, the righthand side of $(1)$ is $O(n^2)$, and since the exponent $\log_43$ is less than $2$, the $\Theta(n^{\log_43})$ term is also $O(n^2)$, making the whole thing $O(n^2)$.