Recitation: Big-Oh

Properties of Big-Oh: -------------------- Recall the definition of Big-Oh: > $f$ is $O(g)$ if there exist constants $c > 0$ and $n_0 > 0$ such that for all > $n \geq n_0$, $f(n) \leq cg(n)$. Here is an example proof that $n$ is $O(2^n)$: > Claim: there exists $c > 0$ and $n_0 > 0$ such that for all $n \geq n_0$, > $n \leq c2^n$. > > Proof: let $c = 1$ and let $n_0 = 1$. We must prove that for all $n ≥ n_0$, > $n \leq 2^n$; we will prove this by induction on $n$. > > In the base case, $n = 1$, and we can verify that $n = 1 \leq 2 = 2^n$. > > For the inductive step, choose a specific $n$ and assume that $n \leq 2^n$ (the > inductive hypothesis). We wish to show that $n+1 \leq 2^{n+1}$. By the > inductive hypothesis, we know that $n + 1 \leq 2^n + 1$. Since $n > 1$, we have > $1 < 2^n$, so $2^n + 1 < 2^n + 2^n = 2^{n+1}$. Thus $n+1 \leq 2^{n+1}$ as > required. **Exercise**: Prove that $n^2$ is $O(n^3)$. **Exercise**: Prove that $O$ is reflexive, that is, prove that for any function $f$, $f$ is $O(f)$. **Exercise**: Prove that $O$ is transitive, that is, prove that if $f$ is $O(g)$ and $g$ is $O(h)$ then $f$ is $O(h)$. **Exercise (\*)**: Prove that if $f$ is $O(f')$ and $g$ is $O(g')$ then $fg$ is $O(f'g')$. Deriving bounds on running time ------------------------------- In order to determine the asymptotic running time of a program, we first need to find constraints on the actual running time of the program. We start with the following assumption: > There is some constant $S$ > such that every step in the small-step substitution model semantics takes time > less than or equal to $S$. *(A previous version of this recitation wrote $c_{step}$ instead of $S$; we have simplified the notation in part to avoid a type-setting bug.)* This means, for example, that doing a primitive arithmetic operation (like $+$), forming a tuple, record, or variant from a given value, branching on a value in an `if` or `match` expression, and calling a function (but not evaluating it all the way to a value!) are all constant time operations. **Exercise**: For each of the following expressions $e$, let $t$ be the total amount of time it takes to evaluate $e$ to a value. Give an upper bound on $t$ in terms of $S$. - `4 * (3 + 5)` (answer: $t \leq 2S$) - `let x = 3 in x + x` - `let x = 3 + 3 in x + x` - `let f x = x + x in f (f 3)` We are often more interested in giving bounds on the running time of a function in terms of the size of the input. **Exercise**: `let f x = x + x`. Let $T(x)$ denote the running time of `f` on input `x`. Give a bound relating $T(x)$ to $S$. Deriving bounds on recursive functions -------------------------------------- Functions that are not recursive (and don't call any recursive functions or use loops) will always run in constant time. To analyze any interesting OCaml functions, we need to find bounds on recursive functions. Consider the following example: ``` let rec countdown n = if n = 0 then () else countdown (n-1) ``` As above, let $T(n)$ be the time it takes to run `countdown` on input $n$. We can directly compute a bound on $T(0)$: ``` countdown 0 --> if 0 = 0 then () else countdown (n-1) --> if true then () else countdown (n-1) --> () ``` Since `countdown 0` takes three small steps, $T(0) \leq 3S$. But what about $T(n)$ for $n > 0$? We can use the substitution model: ``` countdown n --> if n = 0 then () else countdown (n-1) --> if false then () else countdown (n-1) --> countdown (n-1) --> countdown n' -->* v ``` where $n' = n - 1$. We know that it takes 4 steps to evaluate to countdown n'. It then takes $T(n') = T(n-1)$ steps to evaluate `countdown n'` to a value. Thus we see that $T(n) \leq 4S + T(n-1)$. This kind of formula (relating the value of a function on different inputs) is called a **recurrence relation**. **Exercise**: Write down a recurrence relation bounding the running time of the following functions on input $n$: - `let rec fact n = if n <= 1 then 1 else n * fact (n-1)` - `let rec fib n = if n = 0 || n = 1 then 1 else fib (n-1) + fib (n-2)` - `let rec bits n = if n = 0 then 0 else 1 + bits (n/2)` **Exercise**: Write down a recurrence relation bounding the running time of the following functions on an input list of length $n$: - `let rec length l = match l with | [] -> 0 | _::tl -> 1 + length tl` - `let rec map f x = match l with | [] -> [] | h::tl -> (f h)::(map f tl)` (assume that `f` takes less than $T_f$ time on any input)