Time and Space Complexity + Algorithm to Add $n$ Naturals

Definitions

• Time Complexity: asymptotic number of basic operations (steps) as function of input size $n$, $T(n)$.
• Space Complexity: asymptotic total memory (input + auxiliary + recursion stack) $S(n)$; often reported as auxiliary space (extra beyond input).

Algorithm — Sum of First $n$ Natural Numbers

Iterative $O(n)$ time, $O(1)$ aux space:

Algorithm SumNatural(n):
  sum ← 0
  for i ← 1 to n:
    sum ← sum + i
  return sum

Time: $n$ iterations × $O(1)$ → $T(n)=\Theta(n)$ ($n$ additions). Space: variables $sum$, $i$, $n$ → 3 words → $S(n)=\Theta(1)$ auxiliary ($\Theta(n)$ if counting input array? Here input is just $n$ → $O(1)$).

Formula $O(1)$ time (mathematical):

Algorithm SumFormula(n):
  return n*(n+1)//2

Time $\Theta(1)$ arithmetic operations, space $\Theta(1)$. Uses closed form $\sum_{i=1}^n i = n(n+1)/2$.

Recursive (for illustration):

RecSum(n): if n==1 return 1 else return n + RecSum(n-1)

Time $\Theta(n)$, stack space $\Theta(n)$ due to $n$ frames — worse.

Analysis Summary

Variant	Time	Auxiliary Space	Total Space
Iterative loop	$\Theta(n)$	$O(1)$	$O(1)$
Formula	$\Theta(1)$	$O(1)$	$O(1)$
Recursive	$\Theta(n)$	$\Theta(n)$ stack	$\Theta(n)$

Best practical: formula $O(1)$. If required to demonstrate space complexity concept, loop shows $O(1)$ auxiliary despite $O(n)$ time.