Answer or Guide me Through This Question. Show that the function is ϴ(n^4) by first showing that it is O(n^4) and then by showing it it also Ω(n^4)

Question

Show that the function $$ f(n) = \sum_{i=1}^n \sum_{j=1}^i \sum_{k=1}^j k $$ is $\Theta(n^4)$ by first showing that it is $O(n^4)$ and then by showing it is also $Ω(n^4)$.

So I know that:

• $\sum_{i=1}^n i = \frac{n(n +1)}{2}$ which is $\Theta(n^2)$

• To show that $f(n)$ is $O(n^4)$, I need to use the format $f(n) \le c n^4$, where $c > 0$, when $n \ge n_0$.

• To show that $f(n)$ is $\Omega(n^4)$, I need to use the format $f(n) \ge c n^4$, where $c > 0$, when $n \ge n_0$.

Now, I am unsure what to do with the sigmas. I have literally been researching on how to do this problem for 2 days. I am dead and lost. GIVE ME YOUR KNOWLEDGE! Please help!

Answer 1

• You could expand out $f(n)$ to get an actual expression, then show that expression is $\Theta(n)$. start from the identity you already know, substitute it into the expression for $f(n)$, and then go from there. That is, $$ f(n) = \sum_{i=1}^n \sum_{j=1}^i \left( \sum_{k=1}^j k \right) = \sum_{i=1}^n \sum_{j=1}^i \frac{j (j - 1)}{2} .$$ Now, if you expand that out, you'll get one term that you know how to handle again and one term that will need a different identity. This will take either just knowing another identity, or a little bit of cleverness to reduce some sums you need to do. This will get you kind of a complicated expression, but (a) then you'll know exactly what the expression is, and (b) it'll be easy to see from that expression that it's $\Theta(n^4)$.

• But the nice thing about big-O is that you don't need to figure out exact expressions for things. Instead, you only need to show that it's less than some constant times $n^4$ (for big enough $n$), and also more than some other constant times $n^4$. In particular, you can change the equation in a way that only makes things bigger to get an upper bound, and in a way that only makes things smaller to get a lower bound.

  For an upper bound, $O(n^4)$: the thing that makes this sum complicated is that the thing you're adding up keeps changing, and also how many times you add it up keeps changing. What if you tweaked those, in ways that only made the sum bigger? For example, summed over more terms (in a way that increases the total sum but also makes things simpler), or increased the thing that you're adding up?