[Solved]: Simplifying a nested sum

Problem Detail: 

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!

Asked By : Impalerz

Answered By : Yuval Filmus

Hint: $$\sum_{i=1}^n \sum_{j=i}^n (n-j) = \sum_{i=1}^n \sum_{j=0}^{n-i} j. $$ At this point, you can either use exact formulas, or notice that for all $d \geq 0$, $$\sum_{k=1}^m k^d = \Theta(k^{d+1}).$$ (If you don't know what a $\Theta(\cdot)$ bound is, suffice it to say that it is a "tight" $O(\cdot)$ bound.)

After you handle the inner sum, you will need to use the same trick of replacing $i$ with $n-i$ in order to handle the outer sum.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41361

3.2K people like this

 Download Related Notes/Documents