-1
$\begingroup$

When we consider the time complexity of an algorithm, we use summations to represent loops. For instance, the following loop through an array of $n$ length:

for i=n downto 1 do
  \\ something
end for

We express this outer loop as $$ \sum^{n}_{i=1} $$ I'm confused why we do this. For instance, when $n=5$, wouldn't that imply that this outer loop runs 15 times? Since $$ \sum^{5}_{1}= 5+4+3+2+1 = 15 $$ But in reality the loop only runs $5$ times?

$\endgroup$

1 Answer 1

3
$\begingroup$

I think you might be slightly confused about what the notation $$\sum_{i=1}^n$$ means. In particular, it doesn't actually mean anything. There needs to be something "inside" (to the right of) the summation sign. If you want to write the sum of the whole numbers from 1 to $n$ in summation notation, you would do so like this:

$$ \sum_{i=1}^n i = 1+2+\ldots+(n-1)+n $$

The idea is that if the \\something in your code has a running time function $t(i)$ where $i$ is which iteration you are on, then you can compute the running time of the whole block of code. In particular, the running time function of the whole block would be $$ T(n) = \sum_{i-1}^n t(i) $$ When \\something takes a constant amount of time, call it $k$, each iteration then $$ T(n) = \sum_{i=1}^n t(i) = \sum_{i=1}^n k = nk = O(n)$$ But if $t(i) = i$ (like for linear sort) then $$ T(n) = \sum_{i=1}^n t(i) = \sum_{i=1}^n i = \frac{n(n+1)}{2} = O(n^2)$$

$\endgroup$
2
  • $\begingroup$ So $\sum^{n}_{i=1}t(i)$ basically says "sum the completion times for all iterations of function $t$"? And if $t(i)$ is constant $k$, as you say, the sum is $nk$ but if $t(i)$ changes incrementally, like in a sorting algorithm, the sum is that Gauss summation? $\endgroup$ May 15 at 18:02
  • 1
    $\begingroup$ Yes, that is correct $\endgroup$ May 15 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.