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 ccdot(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
