Problem 1
Find a real number \(c\) and an \(N_{0} \in \mathbb{N}\) such that \(n^{2}+5 n
Problem 2
Find a real number \(c\) and an \(N_{0} \in \mathbb{N}\) such that \(n^{3}+5
n^{2}+2 n
Problem 3
Find a real number \(c\) and an \(N_{0} \in \mathbb{N}\) such that \(n^{2}+3 n
Problem 4
Find a real number \(c\) and an \(N_{0} \in \mathbb{N}\) such that \(n^{3}-3
n^{2}+4 n
Problem 5
(a) Find a real number \(c\) and an \(N_{0} \in \mathbb{N}\) such that \(n^{2}
Problem 6
For each of the problems (a)-(d) below: (i) Write an algorithm in pseudocode to solve the problem (be sure your algorithm works correctly if \(m=0\) or \(n=0\); it should not make any assignments to clements of the array), and (ii) Calculate how many assignment statements and how many comparisons the algorithm causes to be executed as a function of \(m\) and \(n\). In this case, count assignments to and comparisons of index variables, as well as assignments to and comparisons of positions in the array. Simplify your answers. (a) Initialize all the elements of an \(m \times n\) array to \(0 .\) (b) Initialize all the elements of an \(m \times n\) array that lie on or above the diagonal to \(0 .\) (Here, by "diagonal" we mean positions \([r, c]\) where \(r=c .)\) (c) Initialize all the elements of an \(m \times n\) array that lic above the diagonal to \(0 .\) (d) Initialize all the elements on the diagonal of an \(m \times n\) array on the diagonal to \(0 .\)
Problem 7
It is tempting to compute the complexity of an algorithm by counting statements, as we did with the BubbleSort example, but only keeping track of the number of steps along the way up to \(O\left(^{*}\right)\). This turns out not to work with loops. For example, it is possible that each time through the loop, the number of statements executed is in \(\mathbf{O}(1)\). but that the number of statements executed by a loop of length \(n\) is not in \(\mathbf{O}(n)\). Find an example. (Hint: Each time through the loop, the number of statements executed may be in \(\mathrm{O}(1)\), but the constants \(c\) and \(N_{0}\) may change).
Problem 7
Using the proof of the Corollary 1 to Theorem 1 as a model, find a real number \(c\) and an \(N_{0} \in \mathbb{N}\) such that \(7 n^{4} \in O\left(n^{4}\right)\) for all \(n \in \mathbb{N}\) with \(n \geq N_{0}\)
Problem 9
Is it reasonable to consider all polynomial-time algorithms to be practical? Why, or why not?
Problem 10
10\. Suppose somebody manages to prove that the time taken by some frequently used algorithm is in \(\mathrm{O}\left(n^{n^{n}}\right)\). Why is this probably uninteresting information?
