1-2 Growth of Functions

Standard methods for simplifying the asymptotic analysis of algorithms

Algorithm Analysis

• The running time $T$ is a function of the amount of input $n$, $T(n)=f(n)$

Θ-notation

• $\Theta(g(n))=\{ f(n): 0 \leq c_1g(n) \leq f(n) \leq c_2g(n) \text{ for all }n \geq n_0 \}$
• $f(n)=\Theta(g(n))$ if there is positive constants $c_1, c_2$
• $g(n)$ is an asymptotically tight bound for $f(n)$
• $f(n)$ is nonnegative whenever $n$ is sufficiently large
• $g(n)$ must be asymptotically nonnegative

Example : $f(n)={{1}\over{2}}n^2-3n=\Theta(n^2)=g(n)$

• $c_1n^2 \leq {{1}\over{2}}n^2-3n \leq c_2n^2$ for all $n \geq n_0$
• Dividing by $n^2$
  • $c_1 \leq {{1}\over{2}}-{{3}\over{n}} \leq c_2$
• Right hand inequality
  • Hold for any value of $n\geq 1$ by choosing any constant $c_2 \geq {{1}\over{2}}$
• Left hand inequality
  • Hold for any value of $n \geq 7$ by choosing any constant $c_1 \leq {{1}\over{14}}$
• Thus, by choosing $c_1={{1}\over{14}}, c_2 \geq {{1}\over{2}}, n_0 \geq 7$,
  we can verify that ${{1}\over{2}}n^2-3n=\Theta(n^2)$

---

O-notation

• Given an upper bound on a function
• $O(g(n))=\{f(n): 0 \leq f(n) \leq cg(n) \text{ for all }n \geq n_0\}$
  • There exist positive constants $c$ and $n_0$

---

Ω-notation

• Lower bound on a function
• $\Omega(g(n)) = \{f(n): 0 \leq cg(n) \leq f(n) \text{ for all } n \geq n_0\}$
  • Positive constants $c$ and $n_0$

---

Asymptotic Notation

• We have $f(n)=\Theta(g(n))$
  if and only if $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$

---

Properties of Big-O

• If $T_1(n)=O(f(n))$ and $T_2(n)=O(g(n))$,
  • $T_1(n)+T_2(n) = max(O(f(n)), O(g(n)))$
  • Lower order terms are ignored
• $O(c*f(n))=O(f(n))$
  • Constants are ignored
• Constants and lower order terms may matter especially when the input size is small
• For large $n$, dominant term is usually indicative of algorithm's behavior
• For small $n$, typically programs on small inputs run so fast we don't care anyway