---
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
---
An algorithm specifies how to compute an output from its inputs. For Contains, the input is a finite array $L$ and a value $v$. The result should be true exactly when $v \in L$.

This is the full-scan algorithm from <ref slug="@content/thoughts/university/twenty-three-twenty-four/sfwr-2c03/L1.pdf">, transcribed into Python:



```python
def contains(values: list[int], target: int) -> bool:
  i, r = 0, False
  while i != len(values):
    if values[i] == target:
      r = True
    i += 1
  return r
```

It keeps scanning after a match. Finding a match changes the flag; it leaves the loop guard unchanged.

## invariants

An invariant describes what holds every time execution reaches the loop guard. Here $L$ is the unchanged input array, $n=|L|$, and $v$ is the target:

$$
0 \leq i \leq n
\quad\land\quad
\bigl(r \iff \exists j\in\mathbb{Z}\;(0 \leq j<i \land L[j]=v)\bigr).
$$

The flag records whether the already-scanned prefix contains the target. The index gives the boundary between that prefix and the remaining elements.

1. **Initialization.** Before the first guard, $i=0$. The scanned prefix is empty, so the existential claim is false and agrees with $r=\mathrm{false}$.
2. **Preservation.** Suppose the invariant holds and the guard is true. Then $i<n$, so reading $L[i]$ is safe. A match makes the flag true. If this element differs from the target, the flag retains its previous value. Incrementing $i$ extends the scanned prefix by exactly that element, preserving both clauses.
3. **Exit.** When the guard is false, $i=n$. The scanned prefix is the whole array, so $r$ answers the membership question.

The condition needs both clauses. The index bound proves the next access is valid; the flag clause connects the execution to the promised result.

For termination, use the bound function, also called a loop variant,

$$
f=n-i.
$$

It is a nonnegative integer whenever the invariant holds. Each iteration reduces it by one. While the guard is true it is positive, so the loop reaches zero and exits after exactly $n$ iterations. The same argument covers an empty array: its initial guard is already false.

## correctness.

A correctness claim needs a contract.

- **Precondition:** the input is a finite array, element equality is defined, and the array remains unchanged during the call.
- **Postcondition:** the returned Boolean is true exactly when the target occurs in the input array.

Initialization, preservation and the exit argument establish _partial correctness_: if the function returns, its result satisfies the contract. The decreasing bound establishes termination. Together they give _total correctness_. See also [Cornell’s loop-invariant proof obligations](https://www.cs.cornell.edu/courses/cs2112/2015fa/lectures/lec_loopinv/).

Specifying the input array matters. Clearing the array and returning false would answer membership in the cleared array while violating the original problem.

## complexity.

Choose what to count before assigning a cost. Use a unit-cost model in which an index fits in a machine word, and array access, integer operations and element equality take constant time. For the Python example, this assumes fixed-size integer values. Comparing arbitrarily long integers or strings needs an additional cost model.

The function performs exactly $n$ element comparisons and evaluates the loop guard $n+1$ times. Its best and worst running times are both $\Theta(n)$ because every input of length $n$ is fully scanned.

The lecture counts initialization as two primitive instructions, each guard as two, each element test as three, each increment as two, and the return as one. If $k$ elements match, assigning the flag adds another $k$ instructions:

$$
C(n,k)=2+2(n+1)+3n+2n+1+k=5+7n+k,
\qquad 0 \leq k \leq n.
$$

Thus the lecture’s $5+7n$ count applies when the target is absent. It is a count under those chosen charges, rather than elapsed time or a Python bytecode count.

Only the index and Boolean flag are stored in addition to the input. The **auxiliary space** is $\Theta(1)$ machine words. The array itself takes $\Theta(n)$ words. Counting index bits instead would require $\Theta(\log(n+1))$ bits for the index.

### runtime.

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

Growth rates describe how costs scale. They leave constants and small-input effects unspecified.

![[thoughts/university/twenty-three-twenty-four/sfwr-2c03/images/growth.webp|Growth]]

For eventually nonnegative cost functions, the constants below are fixed independently of $n$.

> \[!note\] upper bound
>
> $$
> f \in \mathcal{O}(g)
> \iff
> \exists c>0,\;n_0\in\mathbb{N}\;
> \forall n\geq n_0:\quad 0\leq f(n)\leq c\,g(n).
> $$

> \[!note\] lower bound
>
> $$
> f \in \Omega(g)
> \iff
> \exists c>0,\;n_0\in\mathbb{N}\;
> \forall n\geq n_0:\quad 0\leq c\,g(n)\leq f(n).
> $$

> \[!note\] tight asymptotic bound
>
> $$
> f \in \Theta(g)
> \iff
> \exists c_1,c_2>0,\;n_0\in\mathbb{N}\;
> \forall n\geq n_0:\quad
> 0\leq c_1g(n)\leq f(n)\leq c_2g(n).
> $$

For the full scan, $7n\leq C(n,k)\leq13n$ whenever $n\geq1$. Those constants prove the linear bound. Big O and Omega describe bounds on a chosen cost function; they do not themselves mean worst case and best case.

A quadratic cost eventually exceeds a linear cost with fixed positive coefficients. That gives a scalability comparison under the model. The crossover in seconds depends on the implementations and hardware. Early-return linear search also has a different best case: an immediate match takes constant time, while an absent target still requires a full scan.