Help me understand this algorithm problem.

Question

First, I'm not looking for an answer here, I'm just looking to understand the problem so that I can prove it. I'm trying to analyzing the worst case running time of an algorithm, and it must has summation notation. What keeping me back is that I don't understand how to express doSomething(n-j) in summation ( I know that doSomething(k) takes c * k operations for some constant c > 0 (stated in the problem), so it is not constant in this case). The other two loops have starting points (e.g. i = 1 or j = i). Anyway, the pseudo-code is stated blow:

function(n)
    for int i from 1 to n
        for int j from i to n
           doSomething(n - j)
        endfor
    endfor
endfunction

I can express the nested for loop in summation as follow:

$\sum_{i=1}^n \sum_{j=i}^n doSomething(n-j)$

I think I need one more summation, it's just that I don't know how to express it, maybe something like:

$\sum_{k=?}^{n-j}$

I could be wrong here. Could anyone please provide me with some hints in this problem? Thanks a lot.

EDIT: since doSomething(k) takes c * k operations, can I express it as follow:

$\sum_{i=1}^n \sum_{j=i}^n c*k$

Answer 1

You can, instead of $doSomething(n-j)$, write $c\cdot (n-j)$ since that is how many operations will be performed. So the total number of operations is

$$\sum_{i=1}^n\sum_{j=i}^nc\cdot (n-j)=c\cdot \left(\sum_{i=1}^n\sum_{j=i}^n(n-j)\right)$$

Now, first evaluate the inner sum:

$$\sum_{j=i}^n (n - j)$$

This is a sum of all numbers between $0$ and $n-i$, so it is equal to $$\sum_{k=0}^{n-i} k$$

Can you take it from here?

Answer 2

If doSomething(k) takes ck operations for some constant c>0, then it takes c(n-j) operations to do doSomething(n-j), where j is given by the previous loop.

That is, doSomething(n-j) has complexity $O\left(\sum_{k=1}^{n-j}c\right)$, since $\sum_{k=1}^{n-j}c =c(n-j).$

Now, the entire algorithm has complexity $$O\left( \sum_{i=1}^n \sum_{j=i}^n \sum_{k=1}^{n-j}c \right).$$