A function \(f(n)\) belongs to the set \(\Theta(g(n))\) if there exist positive constants \(c_1\) and \(c_2\) such that it can be “sandwiched” between \(c_1g(n)\) and \(c_2g(n)\), for sufficiently large \(n\).
\(\Theta(g(n))\) is a set, then, \(f(n) \in \Theta(g(n))\), but we write: \(f(n) = \Theta(g(n))\)
For all \(n \geq n_0\), \(f(n)\) is equal to \(g(n)\) to within a constant factor
\(g(n)\) is an asymptotically tight bound for \(f(n)\)
By definition, \(\Theta(g(n))\) requires every member \(f(n) \in \Theta(g(n))\) be asymptotically nonnegative
\(f(n)\) nonnegative when \(n\) is sufficiently large
\(\Theta\)-notation
Using the formal definition
Example of using the \(\Theta\)-notation
In function \(\frac{1}{2}n^2 - 3n = \Theta(n^2)\)
Determine positive constants \(c_1\), \(c_2\), and \(n_0\) such that \(c_1n^2 \leq \frac{1}{2}n^2 - 3n \leq c_2n^2\)
dividing by \(n^2\), \(c_1 \leq \frac{1}{2} - \frac{3}{n} \leq c_2\)
For case \(c_1 \leq 1/2 - 3/n\)
Because \(c_1\) is a positive constant, then, \(0 < 1/2 - 3/n\), then \(n > 6\)
then, if \(n_0 = 7\) then \(c_1 \leq 1/2 - 3/7\), which is equal to \(c_1 \leq 1/14\). Let \(c_1 = 1/14\)
\(\Theta\)-notation
Determine positive constants \(c_1\), \(c_2\), and \(n_0\) such that \(c_1n^2 \leq \frac{1}{2}n^2 - 3n \leq c_2n^2\)
For case \(1/2 - 3/n \leq c_2\), when \(n \rightarrow \infty\) then, \(1/2 - 3/n \rightarrow 1/2\), then, \(c_2 = 1/2\)
For \(c_1 = 1/14\), \(c_2 = 1/2\) and \(n_0 = 7\), it holds that \(f(n) \in \Theta(n^2)\) or \(\frac{1}{2}n^2 - 3n = \Theta(n^2)\)
other constants exist!
\(O\)-notation
The \(O\) notation denotes an asymptotic upper bound
For a function \(g(n)\) we denote \(O(g(n))\) and say: big-oh of g of n, or oh of g of n
\(O(g(n))\) also refers to a set of functions
\(O(g(n)) = \{ f(n) :\) there exist positive constants \(c\) and \(n_0\) such that \(0 \leq f(n) \leq cg(n)\)\(\forall\)\(n \geq n_0 \}\).
Use \(O\)-notation to give upper bound on a function, to within a constant factor
Note that \(f(n) = \Theta(g(n))\) implies \(f(n) = O(g(n))\)
\(\Theta\)-notation is stronger than \(O\)-notation
\(O\)-notation
Given a function \(g(n)\), we denote as \(O(g(n))\) to the set of functions such that:
\(O\)-notation
We often describe the running time of an algorithm by inspecting the algorithm’s overall structure
We use \(O\)-notation
A doubly nested loop structure shows an \(O(n^2)\) upper bound on the worst case running time
\(\Omega\)-notation
\(\Omega\)-notation provides an asymptotic lower bound
For a function \(g(n)\), we denote \(\Omega(g(n))\) and say: big-omega of g of n or omega of g of n
\(\Omega(g(n))\) also refers to a set of functions
\(\Omega(g(n)) = \{ f(n) :\) there exist positive constants \(c\) and \(n_0\) such that \(0 \leq cg(n) \leq f(n)\)\(\forall\)\(n \geq n_0 \}\). Use \(\Omega\)-notation to give lower bound on a function, to within a constant factor
Note that \(f(n) = \Theta(g(n))\) also implies \(f(n) = \Omega(g(n))\)
\(\Theta\)-notation is stronger than \(\Omega\)-notation
\(\Omega\)-notation
Given a function \(g(n)\), we denote as \(\Omega(g(n))\) to the set of functions such that:
\(\Omega\)-notation
Theorem 3.1
For any two functions \(f(n)\) and \(g(n)\), we have \(f(n) = \Theta(g(n))\) if and only if \(f(n) = O(g(n))\) and \(f(n) = \Omega(g(n))\).
\(\Omega\)-notation
If we say the running time of an algorithm is \(\Omega(g(n))\), we mean:
No matter what particular input of size n is chosen for each value of n, the running time on that input is at least a constant times \(g(n)\) for sufficiently large \(n\)
We can also mean best-case times, as in insertion sort is \(\Omega(n)\).
Insertion Sort belogs to both, \(\Omega(n)\) and \(O(n^2)\)
Asymptotic Notation in Equations and Inequalities
In \(n = O(n^2)\), the \(=\) sign means set membership: \(n \in O(n^2)\)
When we use asymptotic notation in a formula, we interpret it as representing a function for which we don’t care about its name, only its order
In \(2n^2 + 3n + 1 = 2n^2 + \Theta(n)\) means \(2n^2 + 3n + 1 = 2n^2 + f(n)\), where \(f(n)\) is a function in the set \(\Theta(n)\)
The upper bound \(O-notation\) may or may not be asymptotically tight
\(2n^2 = O(n^2)\) is asymptotically tight
\(2n = O(n^2)\) is not asymptotically tight
We use \(o-notation\) to denote an upper bound that is not asymptotically tight
We define \(o(g(n))\) and say little-oh of g of n as the set \(o(g(n)) = \{ f(n) :\) for any positive constant \(c > 0\), there exists a constant \(n_0 > 0\) such that \(0 \leq f(n) < cg(n)\)\(\forall\)\(n \geq n_0 \}\).
Example, \(2n = o(n^2)\) but \(2n^2 \neq o(n^2)\).
\(\omega\)-notation
\(\omega\)-notation is to \(\Omega\)-notation as \(o\)-notation is to \(O\)-notation
Use \(\omega\)-notation to denote a lower bound that is not asymptotically tight
\(f(n) \in \omega(g(n))\) if and only if \(g(n) \in o(f(n))\).
Formally
\(\omega(g(n)) = \{ f(n) :\) for any positive constant \(c > 0\), there exists a constant \(n_0 > 0\) such that \(0 \leq cg(n) < f(n)\)\(\forall\)\(n \geq n_0 \}\).
\(n^2/2 = \omega(n)\)
\(n^2/2 \neq \omega(n^2)\)
Comparing functions
Many relational properties of real numbers also apply to asymptotic comparisons
Comparing functions
Properties of Asymptotic Functions
Comparing functions
Properties of Asymptotic Functions
Comparing functions
Properties of Asymptotic Functions
Comparing functions
Analogy between asymptotic comparison of 2 functions \(f\) and \(g\) and comparison of 2 real numbers \(a\) and \(b\):
Comparing functions
Trichotomy: for any 2 real numbers \(a\) and \(b\), exactly one of the following must hold: \(a < b\), \(a = b\), or \(a > b\)
NOT all functions are asymptotically comparable
Given 2 functions \(f(n)\) and \(g(n)\), it could be that neither \(f(n) = O(g(n))\) nor \(f(n) = \Omega(g(n))\) holds
Assignment
Review section 3.2, Standard notations and common functions
Review the loop invariant proof for the MERGE procedure used in MergeSort (by the end of section 2.3.1 of the textbook)
