1
$\begingroup$

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$

$\endgroup$

2 Answers 2

2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Thank you! yes, I can take it from here. $\endgroup$
    – ln206
    Apr 13, 2015 at 7:33
2
$\begingroup$

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).$$

$\endgroup$
2
  • $\begingroup$ Thanks! your answer is right and informative but the other person also answered this and he answered before you like 1 min! so I gave him the correct answer. I'm so sorry, I don't have enough reputation to even give you a thumbs up! $\endgroup$
    – ln206
    Apr 13, 2015 at 7:33
  • $\begingroup$ @Impalerz It's no problem! :) Glad to help! $\endgroup$ Apr 13, 2015 at 7:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .