algorithm efficiency

Question

for (int i=1;i<=n;i++){
    for (int j=i;j<=n;j++){
        do_something
    }
}

I need to calculate how many times the "do something" step happens.

I started like so:

$\sum _{i=1}^n\:\sum _{j=i}^n\:1$

I got stuck here trying to open the inner sum. I know that the algorithm is O(n^2) but I find it hard to prove it.

@Student can you explain how you got the last sum? $\sum _{i=1}^n:\sum _{j=i}^n:1 = \sum _{i=1}^n:(n-i+1)$ — DarkLeader, Mar 22 '20 at 21:37
It is from breaking up the summand and substituting with multiplication by $n$ where the same expression is repeated $n$ times: $\sum_{i=1}^n (n-i+1) = \sum_i n - \sum_i i + \sum_i 1 = n^2 -\sum_i i + n$. — Student, Mar 22 '20 at 21:50
@Student thanks! can you write an answer to the post so I can select it as an answer? — DarkLeader, Mar 22 '20 at 22:01

Andrei · Accepted Answer · 2020-03-23T01:00:10.653

2

$$\begin{align}\sum _{i=1}^n\:\sum _{j=i}^n\:1&=\sum_{i=1}^n(n-i+1)\\&=n\sum_{i=1}^n1-\sum_{i=1}^ni+\sum_{i=1}^n1\\&=n^2-\frac{n(n+1)}2+n\\&=\frac{n^2}2+\frac {n}2\end{align}$$

edited Mar 23 '20 at 01:00

answered Mar 23 '20 at 00:39

Andrei

37,370

Did you mean $\sum_i i = n (n+1)/2$? – Student Mar 23 '20 at 00:58
Yes. I'll fix it. Thanks – Andrei Mar 23 '20 at 00:59
@Andrei thank you! – DarkLeader Mar 23 '20 at 12:39

algorithm efficiency

1 Answers1