The header could probably be phrased better...

My teacher used the following claim: $$\sum_{i=1}^{n}\theta\left(i\right)=\theta\left(\sum_{i=1}^{n}i\right)$$

It was in an introduction to algorithms course. Theta refers to the asymptomatic notation. Same as big O.

It looked trivial at first, but after thinking about it, im not sure it's true. Or how to prove it.

Assistance would be appreciated

  • 6
    $\begingroup$ Without knowing what $\theta$ is it is impossible to say. $\endgroup$ – copper.hat Oct 26 '18 at 13:08
  • $\begingroup$ Theta as in asymptomatic notation. It's from a course in algorithms $\endgroup$ – AK_ Oct 26 '18 at 13:11

A function $f:\mathbb{N} \to \mathbb{R}$ is said to be $\Theta(n)$ iff there is some $N$, $c_2 \ge c_1 > 0$ such that $c_1 n \le f(x) \le c_2 n$ for all $n \ge N$.

Suppose $f$ is $\Theta(n)$, and $n \ge N$. Let $K = f(1)+\cdots+f(N-1)$ and $S_n = 1+\cdots + n$.

Then we have $c_1 \sum_{k=N}^n n +K = c_1 (S_n-S_{N-1}) +K \le \sum_{k=1}^n f(n) \le c_2 \sum_{k=N}^n n +K = c_2 (S_n-S_{N-1})+K$.

Note that $c_2 (S_n-S_{N-1})+K \le (c_2+K) S_n$, so we have an upper bound.

The lower bound needs a little more finesse: Since $c_1 (S_n-S_{N-1}) +K = S_n ( c_1 -c_1 {S_{N-1} \over S_n} + {K \over S_n})$, and $(-c_1 {S_{N-1} \over S_n} + {K \over S_n}) \to 0$, we can choose $N' \ge N$ such that $(-c_1 {S_{N-1} \over S_n} + {K \over S_n}) \le {1 \over 2} c_1$ and so $c_1 (S_n-S_{N-1}) +K \ge {1 \over 2 } c_1 S_n$.

Hence for $n \ge N'$ we have ${1 \over 2 } c_1 S_n \le \sum_{k=1}^n f(n) \le (c_2+K) S_n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.