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[4]{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