I'm trying to analyze an algorithm of a function, I can express the function in term of summation, but I have no clues on how I could simplify this summation down to get the run-time in tern of big $O$ or $\Theta$. I have this pseudo-code below:
f(n)
for int i = 1 to n
for int j = i to n
doThis(n - j)
end
end
end
Assuming that doThis(k)
takes $c \cdot k$ operations for some constant $c > 0$. I can express the nested for loop in summation as follow:
$\sum_{i=1}^n \sum_{j=i}^n c\cdot(n-j)$
How does one simplify this summation? It has been a while since I touch math so I'm trying to get an idea here. Any help would be appreciated, thank you!