I. Complexity


1. Worst-Case Analysis

Worst-Case Analysis is a function of the input length, and the value of the function is the maximum quantity of resource over all inputs of given length.

⇒ The input length is the length of input string

2. Time Complexity

The time complexity of a TM $M$ is a function:

$$ f:\mathbf{N\rightarrow N} $$

where $f(n)$ is the maximum number of steps $M$ uses on any input of length $n$

$M$ runs in time $f(n)$ ↔ $M$ is a $f(n)$ time TM

Analyze Algorithms

We care about the behaviors on large inputs, hence we won’t mind the fine distinctions.

Measurement

Using asymptotic notation (“Big-Oh Notation”)

Given functions $f, g: \mathbf{N → R^+}$, we say $f(n) = O(g(n))$ if there exist positive integers $c, n_0$ such that for all $n ≥ n_0$:

$$ f(n) \leq cg(n) $$

⇒ $f(n)$ is asymptotic less than or equal to $g(n)$