Explanation of Summations for Algorithm Analysis

Question

I do not have a background in Computer Science, work as a Software Engineer, and am attending college for my Master's degree in Computer Science. I have a data structures and algorithms course that I am taking currently with the "Introduction to Algorithms" text book by Cormen, Leiserson, Rivest, and Stein (CLRS). This is not one of my homework problems, but rather extra effort for me to try and understand algorithm analysis as it relates to using summations.

For instance, consider the example of $T(n) = T(n-2) + n^2$. An answer I saw floating around had $\sum\limits_{i=0}^{n/2} (n-2i)^2$. I can understand how to get the $(n-2i)^2$ part, but am not sure how to get the upper and lower boundary conditions, as well as what to do after this point. I guess the total answer for this is $\Theta(n^3)$, but am not making the connection between the summation and the final answer.

I have had calculus in the past, and do remember some of the series chapter that dealt with harmonic, Taylor, geometric, telescoping, and power series. But as it relates to CS, I'm not quite sure where it is going.

So, my questions are:

1. Why are the lower and upper bounds 0 and n/2, respectively?
2. What do I do with the summation notation to get a final answer?

I'm sure this is easily answered and that I'm just overlooking something. I know that a series that looks like the harmonic series, which is $\sum_{i=1}^n (1/i)$, will give $\ln(n) + O(1)$. But most of it I don't understand how to get the values associated with Big-O, Omega, or Theta.

I appreciate the help, guidance, and any examples/tutorials you can point me to.

Answer 1

I will answer each of your questions as follows

1. Why are the lower and upper bounds 0 and n/2, respectively?

   • For the lower bound: we can see that at the first recursive call, the running time is $n^2$ so $n^2 = (n - 2i)^2$ when $i = 0$
   • For the upper bound: we can see that when a base case is given say $T(1) = a$, ($a$ can be some constant that for the purpose of calculating the upper bound, we don't really care) then to reach to the base case, you will need to apply the recurrence formula $x$ times which means you need to solve for $x$ the equation $((n - 2) - 2) .. -2) = 1$. This equation is $n - 2x = 1$ which will give you $x = \frac{n-1}{2}$. To make things easier for readers, someone might consider the base case is $T(0)$. In this case you will instead solve $n-2x=0$ giving $x=\frac{n}{2}$. This is your convenient upper bound $\frac{n}{2}$.

2. What do I do with the summation notation to get a final answer?

   A good way to solve summation like the one you give for the purpose of asymptotic bounding (such as $O$, $\Omega$, $\Theta$) is using integration. Let's look at the following graph, so you can easily visualize the approach and main idea.

   

   Let's look at the interval where the terms in your summation are monotonic. In your particular case, the terms in your summation decreases as $i$ increases in the interval of $[0, \frac{n}{2})$. This is because the each of the terms is a parabola on variable $i$, and this parabola has a single minima at $i = n/2$. As $i$ increases, the parabola decreases until $i$ reaches $n/2$ then the parabola start increasing.

   Let's not worry too much about the actual value on the y-axis, but focus on the fact that your summation can be view as the summation of all the cyan blocks having width 1. As the terms monotonically decrease, you have $(n - 2i)^2 < (n - 2(i-1))^2$. Then you choose the function $f(x)$ using the right hand side replacing the variable $i$ with the variable $x$ which is the red line in the graph. $f(x)= (n - 2(x-1))^2$ thus you have $\sum\limits_{i=0}^{n/2} (n - 2i)^2 < \int\limits_{0}^{n/2} (n - 2(x-1))^2dx$

   Now you solve the right hand side of the above inequality. This will give you $-\frac{1}{2}\frac{1}{3} (n - 2(x-1))^3 \Big|_{0}^{n/2} = -\frac{8}{6} - (- \frac{1}{2}\frac{1}{3}(n+2)^3) = \frac{(n+2)^3 - 8}{6} \in O(n^3)$. So you have $T(n) \in O(n^3)$

   If you want to find the bound for $\Omega$, then you will do similarly. The difference now is that you choose $f(x) = (n - 2(x+1))^2$ because the terms in the summation are greater than the next term $(n - 2i)^2 > (n - 2(i+1))^2$. Your summation now can be seen as the bigger cyan plus blue (and purple) blocks. In other words, $\sum\limits_{i=0}^{n/2} (n - 2i)^2 > \int\limits_{0}^{\frac{n}{2}-1} (n - 2(x+1))^2dx$. Note that I have changed the upper bound on integration because getting over $\frac{n}{2}-1$ the terms change direction. But that is ok, because we still have the bound on $>$ sign

   Solving the integration will give you a polynomial of degree 3 so you have $T(n) \in \Omega(n^3)$.

   So now you can conclude that $T(n) \in \Theta(n^3)$

   Extra: Back up image in case the graph above is no longer viewable: Summation bound