How to Find the Big-Theta Bound of a Summation

A summation’s Big-Theta bound describes how its total grows as the index limit increases. The main task is to find a function that bounds the sum both above and below, up to constant factors.

The phrase “Big-Theta of a summation” can refer to many different sums, so there is no single answer without the summand and its limits. The method below applies to common finite sums in mathematics and algorithm analysis.

What Θ means

For nonnegative functions, $S(n)=\Theta(g(n))$ means there are positive constants $c_1,c_2$ and an integer $n_0$ such that, for every $n\ge n_0$,

$$c_1g(n)\le S(n)\le c_2g(n).$$

The constants and the starting point do not depend on $n$. Informally, the sum and $g(n)$ have the same growth rate after constant factors are ignored. This is stronger than an upper bound alone: $S(n)=O(g(n))$ gives only the upper inequality.

For a sum $S(n)=\sum_{i=1}^n a_i$, first check whether the terms are nonnegative. If they are, adding or comparing terms usually gives useful bounds. If positive and negative terms cancel, estimate the signed sum itself; the sum of the absolute values may have a different growth rate.

A practical method

1. Simplify the summand. Identify its growth in terms of the summation index. For instance, a term such as $3i^2+4i+1$ grows like $i^2$ for large $i$.
2. Use a known formula or comparison. Exact formulas, inequalities, and integral estimates can turn the sum into upper and lower bounds.
3. Keep the largest-order contribution. For polynomial sums, the highest power usually determines the order. For sums with exponential terms, terms near the largest index may dominate.
4. Prove both bounds. An upper estimate alone does not establish Θ. Find a lower estimate of the same order too.

When each term is nonnegative and $a_i=\Theta(g(i))$ with fixed comparison constants, summing the inequalities shows that $\sum_{i=1}^n a_i=\Theta\bigl(\sum_{i=1}^n g(i)\bigr)$. The constants must apply uniformly across the range being summed; a pointwise intuition about large $i$ is not, by itself, a complete proof.

Worked example: sum of squares

Consider

$$S(n)=\sum_{i=1}^n i^2.$$

For an upper bound, every term is at most $n^2$, and there are $n$ terms. Therefore

$$S(n)\le n\cdot n^2=n^3.$$

For a lower bound, assume $n\ge 2$ and look only at the indices from $\lceil n/2\rceil$ through $n$. There are at least $n/2$ such indices, and each has $i^2\ge (n/2)^2$. Thus

$$S(n)\ge \frac{n}{2}\left(\frac{n}{2}\right)^2=\frac{n^3}{8}.$$

Together, these inequalities give $n^3/8\le S(n)\le n^3$ for $n\ge2$, so

$$\sum_{i=1}^n i^2=\Theta(n^3).$$

The exact identity $S(n)=n(n+1)(2n+1)/6$ gives the same result, but the bounds show how to prove the order without calculating an exact formula.

Useful comparisons

For sums of powers, the standard growth pattern is

$$\sum_{i=1}^n i^p=\Theta(n^{p+1})$$

for fixed $p>-1$. For example, summing terms that grow like $i$ produces order $n^2$, while summing terms that grow like $i^3$ produces order $n^4$.

The harmonic sum behaves differently:

$$\sum_{i=1}^n \frac{1}{i}=\Theta(\log n).$$

This follows by comparing the sum with the integral of $1/x$. A geometric sum such as $\sum_{i=0}^n 2^i$ is instead $\Theta(2^n)$: its last term is already $2^n$, and the full sum is less than $2^{n+1}$.

These examples illustrate why you should examine the summand before applying a rule. A sum of $n$ terms is not automatically $\Theta(n)$; the terms may themselves grow, shrink, or increase exponentially.

Common mistakes

• Proving only an upper bound. Showing $S(n)=O(g(n))$ does not prove $S(n)=\Theta(g(n))$. You also need a lower bound of order $g(n)$.
• Assuming every sum has $n$ equal-size terms. In $\sum i^2$, terms range from $1$ to $n^2$; treating them all as constant-size misses the growth.
• Ignoring cancellation. For example, $\sum_{i=1}^n (-1)^i$ stays bounded, even though the sum of the absolute values is $n$.
• Dropping a term that changes the order. In $\sum_{i=1}^n 1/i$, the individual terms tend to zero, but the total grows like $\log n$, not like a constant.
• Using constants that depend on $n$. The constants in a Θ comparison must be fixed as $n$ grows.

For a particular summation, write down the summand and its index limits first. Then look for an exact formula or establish a pair of comparisons that trap the sum between constant multiples of one candidate growth function.