2
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.