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
$\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?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! yes, I can take it from here. $\endgroup$ – Impalerz Apr 13 '15 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).$$

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Impalerz Apr 13 '15 at 7:33
  • $\begingroup$ @Impalerz It's no problem! :) Glad to help! $\endgroup$ – Andrey Kaipov Apr 13 '15 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.