Question

(a) Give the standard Theta (O(. )) form for each of the following functions. (E.g., 2n + 3 would be written as O(n).) [10 marks] \text { 1. } 5 n^{3}+n^{4}+3 n(\log n)^{10} \text { 2. } 25 \log n+2 n+7777 \text { 3. } 3 \log \left(n^{4}\right) \text { 4. } \frac{n(n+1)(2 n+1)}{6} \text { 5. } 2 n+3 n(\log n)^{2}+2 (b) Put the following Theta classes in order of increasing growth (e.g.,increasing running times). [10 marks] \Theta(\log n), \quad \Theta\left(n^{2}\right), \quad \Theta\left(n^{2} \log n\right), \quad \Theta(1), \quad \Theta(n) \Theta\left(\frac{n^{2}}{\log n}\right), \quad \Theta\left(\sqrt{n^{9}}\right), \quad \Theta\left(2^{n}\right), \quad \Theta\left(n(\log n)^{2}\right), \quad \Theta(n !) :) Following are some big-Oh relationships. For each, give witnesses no and c that can be used to prove the relationship. Choose your witnesses to be minimal, in the sense that no – 1 and c are not witnesses, and ifd < c, then no and d are not witnesses. [9 marks] 16 n^{2} \text { is } \mathcal{O}\left(n^{4}\right) 3^{n+5} \text { is } \mathcal{O}\left(3^{2 n}\right) n^{2} \text { is } \mathcal{O}(n !)  Fig: 1  Fig: 2  Fig: 3  Fig: 4  Fig: 5  Fig: 6  Fig: 7  Fig: 8  Fig: 9  Fig: 10  Fig: 11  Fig: 12  Fig: 13  Fig: 14

### Submit a new Query    Success

Assignment is successfully created  Verified  