03 Degrees of uncertainty

Recall that we write:

• $f(n)=O(g(n))$ if there are $c,n_0\in \mathbb{N}$ such that, whenever $n\ge n_0$, we have $f(n)\le cg(n)$
• $f(n)=\Omega (g(n))$ if $g(n)=O(f(n))$
• $f(n)=\Theta (g(n))$ if $g(n)=O(g(n))$ and $g(n)=O(f(n))$

Example

Let $f(n):=5n^2+17n+3$. Then $f(n)=O(n^3)$, $f(n)=\Omega (n)$ and $f(n)=\Theta (n^2)$.

Example: Satisfiability

Fix a set of propositional variables $\{p_0,p_1,p_2,\cdots \}=\text{Prop}$
Formulas: $A,B,\cdots :=p_i|\neg A|A\wedge B|A\vee B$
Assignment: $\alpha :\text{Prop}\to \{0,1\}$
Eval:

• $\alpha (\neg A)=1-\alpha (A)$
• $\alpha (A\vee B)=\max (\alpha (A),\alpha (B))$
• $\alpha (A\wedge B)=\min (\alpha (A),\alpha (B))$

SAT is the set of formulas $A$ S.T $\exists \alpha :\alpha (A)=1$.

Cost of evaluation

• Each connective takes one time step.
• evaluating a formula under an assignment hits time $O(n)$. ($n$ is the length of the input data)

Cost of satisfiability:

• Input: Formula $A$
• One algorithm to solve: There are $O(2^n)$ assignments to $A$. Just check them all
• This takes time $O(n\cdot 2^n)$, as evaluating is $O(n)$ and the algorithm takes $O(2^n)$.

Example: Sorting

• Input: A string of natural numbers $\sigma :=n_1,n_2,\cdots ,n_k$
• Problem: Determine if the string is already sorted ?
  • Determine $\sigma$ is sorted, i.e., $\forall i<k(n_i\le n_{i+1})$
• One algorithm: check for each $i$, $n_i\le n_{i+1}$
• Linear time $O(n)$