Efficiency

Tractability means having efficient computational solutions
What does “efficient” mean in this sense?
- Originally it meant a solution that runs fast on a machine. However, what machine?
- Then it changed to meaning better performance than the brute force solution for the worst case
- Now an algorithm is considered efficient if it runs in polynomial time (this is the definition of efficiency we use)

Big O

O(n) represents the asymptotic upper bound
Definition: Given functions f(n) and g(n) then $f (n) \in O (g (n))$ if there exists constants $c$ and $n_{0}$ where $0 \leq f (n) \leq c g (n)$ for all $n \geq n_{0}$
In other words, $f (n) \in O (g (n))$ if $f (n)$ doesn’t grow faster than $g (n)$
Growth order of common functions:
- $O (1) < O (lo g (n)) < O (n) < O (n lo g (n)) < O (n^{2}) < O (n^{3}) < O (2^{n}) < O (n!)$
From the definition above, multiple functions can be big-O of another function
- For example, $n \in O (n)$ and $n \in O (n^{2})$
Generally we want to give the tightest upper bound of a function.
- For example, if we have the function $n$ we don’t want to say $n \in O (n^{2})$ even though it’s true. We would rather say $n \in O (n)$ since it’s the tightest upper bound
When giving the $O (n)$ of a function, you take the fastest-growing term and remove the constants from it
- Ex: $4 n^{2} + 2 n lo g (n) + 3 n + 123456 \in O (n^{2})$
Big O does not indicate the worst case of a function

$Ω (n)$ represents the asymptotic lower bound
Definition: Given functions f(n) and g(n), then $f (n) \in Ω (g (n))$ if there exists constants $c$ and $n_{0}$ where $0 \leq c g (n) \leq f (n)$ for all $n \geq n_{0}$
In other words, $f (n) \in Ω (g (n))$ if $f (n)$ doesn’t grow slower than $g (n)$
Like how multiple functions can be O(n) of a function, multiple functions can be $Ω (n)$ of a function
- For example, $n \in Ω (n)$ and $n \in Ω (lo g (n))$
Again, give tightest bound usually
Process for getting big- $Ω$ of a function is the same as getting big-O
Big $Ω$ does not indicate the best case of a function

$Θ (n)$ represents the asymptotic tightest bound of a function
$f (n) \in Θ (g (n))$ if $f (n)$ doesn’t grow faster or slower than $g (n)$
Basically, $f (n)$ should be BOTH $O (g (n))$ and $Ω (g (n))$
To prove something is $Θ (n)$ you must prove that it is both $O (n)$ and $Ω (n)$