# Why do we use summations when computing time complexity?

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?

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)$$
• 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? May 15 at 18:02