1

I am trying to understand the process of finding the complexity of a nested for loop.

I understand all the steps of the solution provided, except for one which I find unintuitive:

$$\sum_{j=1}^n \Theta(j^2) = \Theta\left(\sum_{j=1}^n j^2\right) $$ which then evaluates to $ \Theta(n^3)$.

Is there a simple way to explain this step? What am I missing?

I tried expanding the LHS, which gives $ \Theta(1^2) + \Theta(2^2) + ... + \Theta(n^2) = \Theta(n^3) $.

But i'm unsure on how to do a sum of big theta functions.

Ignoring the big thetas on the LHS or grouping them all within a single big theta (like treating the big theta as a variable, instead of a function) essentially yields the RHS of the step in question, but this method seems haphazard.

Xander Henderson
  • 29,772
Cyruno
  • 65

1 Answers1

3

The step $$ \sum_{j=1}^n\Theta(j^2)=\Theta\Big(\sum_{j=1}^nj^2\Big)$$ is not valid in general, unless it is meant to be interpreted as a sum where each term has the same implicit constants.

Otherwise, the issue is that while for each $j$ there are constants $c_j$ and $C_j$ such that the $j$th term in the sum is $\leq C_jj^2$ and is $\geq c_jj^2$, there is no way to control the growth of the constants without further information.

To give a specific example, if $f_j(k)=jk^2$ for $j=1,2,3,\dots$, then $f_j(k)=\Theta(k^2)$ for each fixed $j$, but $$ \sum_{j=1}^nf_j(j)=\sum_{j=1}^nj^3=\Theta(n^4) \, . $$

If however every term in the sum has the same implicit constants $c$ and $C$, then we are fine, since then $$ c\sum_{j=1}^nj^2\leq \sum_{j=1}^nf_j(j)\leq C\sum_{j=1}^nj^2 \, .$$

carmichael561
  • 53,688
  • Assuming all the implicit constants are the same, I still don't quite understand how to get from a sum of big theta's, to the big theta of a sum, or as you put it: $ c\sum_{j=1}^nj^2\leq \sum_{j=1}^nf_j(j)\leq C\sum_{j=1}^nj^2 , .$ – Cyruno Sep 11 '17 at 05:19
  • If we have three sequences $x_j,y_j,z_j$ such that $x_j\leq y_j\leq z_j$ for all $j$, then $\sum_{j=1}^nx_j\leq \sum_{j=1}^ny_j\leq \sum_{j=1}^nz_j$. Now apply this with $x_j=cj^2$, $y_j$ the $\Theta(j^2)$ term, and $z_j=Cj^2$. – carmichael561 Sep 11 '17 at 05:24