Complexity analysis

algorithm = takes one-or-more values, produces an outputs

Ex: contains

Given a list of $L$ and value $v$, return $v\in L.$

Input: $L$ is an array, $v$ is a value Output: true if $v\in L$, false otherwise

i, r := 0, false
while i neq |L| do
  if L[i] = v then
    r := true
    i := i + 1
  else
    i := i + 1
return r

invariants

Induction hypothesis that holds at beginning of iteration.

Deterministic

1. Base case: inv holds before the loop
2. Hypothesis: holds after j-th, j<m repetition of loop
3. Step: assume inv holds when start m-th loop, proves it holds again at the end of m-th loop

Are we done?

• Assuming invariant → does it reach conclusion
• Does it end?

Formal argument: prove a bound function

bound function $f$ on the state of the algorithm such that the output of $f$

• natural number (0, 1, 2, …)
• strictly decreases after each iteration

$f=|L|-i$ starts at $|L|,|L|\ge 0$

correctness.

1. pre-condition: restriction require on input
2. post-condition: should the output be
3. prove the running the program turns pre-condition and post-condition

complexity.

assume V is not in the list Contains(N) = 5 + 7N

given V is in the list

contains is correct, runtime complexity is $\text{ContainsRuntime(|L|)}=|L|$ and memory complexity is $\text{ContainsMemory(|L|)}=1$

runtime.

models are simplification.

shows different growth rates.

Interested in scalability of algorithm For large enough inputs, contains will always be faster than altc because order of growth of $\text{CRuntime}<\text{AltCRuntime}$

upper bounded (at-most)

$f(n)=\mathcal{O}(g(n))⟺\exists n_0,c>0\mid 0\le f(n)\le c\cdot g(n)\forall n\ge n_0$

lower bounded (at-least)

$f(n)=\Omega (g(n))⟺\exists n_0,c>0\mid 0\le c\cdot g(n)\le f(n)\forall n\ge n_0$

equivalent (strictly bounded)

$f(n)=\Theta (g(n))⟺\exists n_0,c_{lb},c_{ub}\mid 0\le c_{lb}\cdot g(n)\le f(n)\le c_{ub}\cdot g(n)\forall n\ge n_0$