---
date: '2024-01-08'
description: algorithm complexity analysis covering invariants, correctness proofs, runtime and memory complexity, big o, omega, and theta notation.
id: W1
modified: 2026-06-05 15:08:41 GMT-04:00
tags:
  - sfwr2c03
title: Complexity analysis
created: '2024-01-08'
published: '2024-01-08'
pageLayout: default
slug: thoughts/university/twenty-three-twenty-four/sfwr-2c03/W1
permalink: https://aarnphm.xyz/thoughts/university/twenty-three-twenty-four/sfwr-2c03/W1.md
generator:
  quartz: v4.6.0
  hostedProvider: Cloudflare
  baseUrl: aarnphm.xyz
full: https://aarnphm.xyz/llms-full.txt
---
> 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

```prolog
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.

[[thoughts/Determinism|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 <span>&rarr;</span> 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| \geq 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.

![[thoughts/university/twenty-three-twenty-four/sfwr-2c03/images/compare-graphs.webp|graph comparison]]

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}$_
> ![[thoughts/university/twenty-three-twenty-four/sfwr-2c03/images/growth.webp|Growth]]

> \[!note\] _upper bounded (at-most)_
>
> $f(n) = \mathcal{O}(g(n)) \iff \space \exists \space n_{0}\ , c>0 \mid 0 \leq f(n) \leq c \cdot g(n) \space \forall \space n \geq n_{0}$

> \[!note\] _lower bounded (at-least)_
>
> $f(n) = \Omega(g(n)) \iff \space \exists \space n_{0}\ , c>0 \mid 0 \leq c \cdot g(n) \leq f(n) \space \forall \space n \geq n_{0}$

> \[!note\] _equivalent (strictly bounded)_
>
> $f(n) = \Theta(g(n)) \iff \space \exists n_{0}, c_{lb}, c_{ub} \mid 0 \leq c_{lb} \cdot g(n) \leq f(n) \leq c_{ub} \cdot g(n) \forall n \geq n_{0}$