Order of a Loop's Accumulated Output (Summation Magnitude)

The distinction that traps everyone

Many konkur items ask for the order of the printed value of an accumulator (k, j, s, ...), not the running time. The two are different: a doubly nested loop runs in $\Theta(n^2)$ time, but the number it accumulates can be $\Theta(n^4)$, $\Theta(2^n)$, or anything else, depending on what is added or multiplied each step. Always re-read the question: "order of the output" means analyze the final value of the variable, not the loop count.

The recipe

1. Express the accumulator as a sum or product over the loop indices. A variable updated by += becomes a $\sum$; one updated by *= becomes a $\prod$.
2. Pin down each index range by tracing the loop guards (mind whether a counter is updated before or after it is used).
3. Collapse the closed form with the standard identities below.
4. Keep only the dominant term to get the $\Theta$-order (for a printed value, report the order, e.g. $\Theta(n^4)$; for an exact value, simplify fully).

Power-sum identities (the additive toolbox)

$\sum_{i=1}^{n} i = \frac{n(n+1)}{2} = \Theta(n^{2}),\qquad \sum_{i=1}^{n} i^{2} = \frac{n(n+1)(2n+1)}{6} = \Theta(n^{3}),$ $\sum_{i=1}^{n} i^{3} = \left(\frac{n(n+1)}{2}\right)^{2} = \Theta(n^{4}),\qquad \text{in general } \sum_{i=1}^{n} i^{p} = \Theta\!\left(n^{\,p+1}\right).$ For a sum, only the highest power survives in $\Theta$: $\tfrac12\sum (i^3+i^2)=\Theta(n^4)$ because $\sum i^3$ dominates $\sum i^2$.

Exponent-sum identity (the multiplicative toolbox)

When the accumulator is a product of powers of a fixed base, the exponents add: $\prod_{t=1}^{k} b^{\,e_t} = b^{\,\sum_{t=1}^{k} e_t}.$ The most common pattern is consecutive exponents, where the exponent sum is again triangular: $\prod_{t=1}^{k} b^{\,t} = b^{\,1+2+\cdots+k} = b^{\,k(k+1)/2}.$ A product grows exponentially in the loop count — never confuse it with the polynomial growth of a sum.

Mini-example (additive)

s = 0
for(i = 1, i <= n, i++)
    for(j = 1, j <= i, j++)
        s = s + j

Inner loop adds $\sum_{j=1}^{i} j = \tfrac{i(i+1)}{2}$. Then $s = \sum_{i=1}^{n}\frac{i(i+1)}{2} = \frac12\sum_{i=1}^{n}(i^{2}+i) = \Theta(n^{3}).$ The running time is only $\Theta(n^2)$, but the printed value is order $n^{3}$.

Mini-example (multiplicative)

If $p$ is multiplied by $2^t$ on pass $t$ for $t=1,\dots,k$, then $p = \prod_{t=1}^{k} 2^{t} = 2^{k(k+1)/2}$ — exponential in $k$.

Pitfall: "Order of the output" $\neq$ "time complexity." A counter incremented inside the inner loop measures steps ($\Theta(n^2)$ here), but the value built by adding $i\cdot j$ can be a full degree higher ($\Theta(n^4)$). Decide first whether you are counting iterations or summing what each iteration contributes.