Analysing Function Costs

Summary of function complexities

Function	Time	Space	Notes
npower	O(n)	O(n)	n multiplications, not tail-recursive
nsum	O(n)	O(n)	n additions, not tail-recursive
summing	O(n)	O(1)	Iterative with accumulator
n(n+1)/2	O(1)	O(1)	Closed form
power	O(log n)	O(log n)	Binary exponentiation
sillySum	O(2ⁿ)	O(n)	Calls itself twice per step

Deriving recurrences from OCaml

Consider nsum:

let rec nsum n =
  if n = 0 then 0
  else n + nsum (n - 1)

Given n+1, it performs constant work (addition and subtraction) and calls itself with n. The recurrence:

$T(0) = 1$ $T(n+1) = T(n) + 1$

The closed form is $T(n) = n + 1$, giving O(n).

nsumsum: O(n²)

let rec nsumsum n =
  if n = 0 then 0
  else nsum n + nsumsum (n - 1)

The recurrence: $T(n+1) = T(n) + n$. Closed form:

$T(n) = (n-1) + \dots + 1 = \frac{n(n-1)}{2} = O(n^2)$

power: O(log n)

power divides n by 2 each step: $T(n) = T(n/2) + 1$. Since $T(2^n) = n+1$, we have $T(n) = O(\log n)$.

sillySum: O(2ⁿ)

let rec sillySum n =
  if n = 0 then 0
  else n + (sillySum (n-1) + sillySum (n-1)) / 2

Each recursive step makes two recursive calls. The function calls itself 2ⁿ times total. This is exponential — doubling hardware lets us go from n to n+1, which is practically useless.

The fix: use a let binding to compute a value once and reuse it:

let x = 2.0 in
let y = Float.pow x 20.0 in
y *. (x /. y)

Here y is computed once and used twice, avoiding the exponential blow-up.

Space vs time

• Space complexity can never exceed time complexity (it takes time to use space)
• Time complexity often greatly exceeds space complexity
• For example, sillySum is O(2ⁿ) time but only O(n) space (maximum call depth)
• Tail recursion reduces space, not time