Exercises 6.2 Exercises
1.
Arrange the following functions in ascending order of growth rate: \(n^2\text{,}\) \(\log n\text{,}\) \(n!\text{,}\) \(n \log n\text{,}\) \(n^3\text{,}\) \(1\text{,}\) \(n\text{.}\) Assign each a number starting with 1 for the slowest-growing function, and if two functions are big-O of each other then assign them the same number.
2.
Arrange the following functions in ascending order of growth rate: \(2n+1\text{,}\) \(n^2+n\text{,}\) \(2^n \log n\text{,}\) \(2^n+100\text{,}\) \(n^2\log n\text{,}\) \(503\text{.}\) Assign each a number starting with 1 for the slowest-growing function, and if two functions are big-O of each other then assign them the same number.
3.
Arrange the following functions in ascending order of growth rate: \(4000\log n\text{,}\) \(2n^2+13n-8\text{,}\) \(1036\text{,}\) \(3n \log n\text{,}\) \(2^n-n^2\text{,}\) \(2n!-n\text{,}\) \(n^2-4n\text{.}\) Assign each a number starting with 1 for the slowest-growing function, and if two functions are big-O of each other then assign them the same number.
4.
Arrange the following functions in ascending order of growth rate: \(7n-1+n^3\text{,}\) \(n!\text{,}\) \(2^n\text{,}\) \(2^n n!\text{,}\) \(2^n + n!\text{,}\) \(403790\text{,}\) \(403790n^3 - n^2 + n + 1\text{.}\) Assign each a number starting with 1 for the slowest-growing function, and if two functions are big-O of each other then assign them the same number.
5.
Give the simplest function \(b_n\) of lowest order such that \(4n^3+3n^2 \log n=O(b_n)\text{.}\)
6.
Give the simplest function \(b_n\) of lowest order such that \((8n^3 + 20n)(2^n + 4\log n)=O(b_n)\text{.}\)
7.
Let \(a_n = n^3 + n^6 + 8n^5\log n\text{.}\) Give the simplest function \(b_n\) of lowest order where \(a_n=O(b_n)\text{.}\)
8.
Let \(a_n = 100n + 5n^3\log n - n^2 + \log n\text{.}\) Give the simplest function of lowest order \(b_n\) such that \(a_n=O(b_n)\text{.}\)
9.
Suppose that \(a_n= (8n+n^2)(5n+\log n+n \log n)(3n-8n^5+n!)\text{.}\) Give the simplest function \(b_n\) of lowest order where \(a_n=O(b_n)\text{.}\)
10.
Suppose that \(a_n = (n^3-n)(100 \log n + n^2 \log n)(n^{5}+5^n+5n)\text{.}\) Give the simplest \(b_n\) of lowest order where \(a_n=O(b_n)\text{.}\)
11.
It turns out that \(n^2+3n+1\) big-O of \(n^2\text{.}\) This means that there exist integers \(k\) and \(C\) where for all \(n \ge k\text{,}\) \(n^2+3n+1 \le Cn^2\text{.}\) Find values for \(k\) and \(C\) that make this inequality true. You may use this Desmos applet to choose an appropriate value of \(C\text{.}\)
Hint.Hint: You are looking for a value of \(C\) where there is some \(k\) where for all \(x \ge k\text{,}\) the graph of the function \(x^2+3x+1\) is below the graph of the function \(Cx^2\text{.}\)
Solution: There are several, but one is \(C=3\) and \(k=2\text{.}\)