Theta Notation

Tags

comp-sci

An asymptotic function which provides a tight [see page 9, upper and lower] bound. A function \( f(n) \) belongs to the set \( \theta(g(n)) \) if it can be sandwiched between \( c_1 g(n) \) and \( c_2 g(n) \) for sufficiently large \( n \).

\begin{align*} \theta(g(n)) = \{ f(n) : & \text{\; there exists constants \;} 0 < c_1 \leq c_2 \text{\; and \;} n_0 \text{\; such that \;} \\

                  & 0 \leq c\_1 g(n) \leq  f(n) \leq c\_2g(n) \text{\\; for all \\;} n \geq n\_0 \\}

\end{align*}

Proving θ-notation example

For [see page 10, example] consider the function \( \frac{3}{2}n^2 + \frac{7}{2}n - 4 = \theta(n^2) \).

To show this we must find constants \( c_1, c_2, n_0 \) such that: \[ 0 \leq c_1 n^2 \leq \frac{3}{2} n^2 + \frac{7}{2}n -4 \leq c_2 n^2 \]

Firstly we can divide through by \( n^2 \) to get \[ 0 \leq c_1 \leq \frac{3}{2} + \frac{7}{2n} - \frac{4}{n^2} \leq c_2 \] This inequality can be shown to hold for \( c_1 = \frac{3}{2}, c_2=2, n_0 = 7 \), therefore it's true.

Observe: that it's impossible to [see page 12, prove] the claim \( \frac{3}{2}n^2 + \frac{7}{2}n - 4 = \theta(n) \) because there are no constants \( c_2 \) such that \( \frac{3}{2}n^2 + \frac{7}{2}n - 4 \leq c_2 n \) for all \( n \geq n_0 \).