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$