Socrative Quiz

Professor Arugorizumu has been studying the computational problem of smettlefying prime Jacobians¹. He has published a clever $\mathrm{\Theta }(n^3)$ algorithm, but he is convinced he is on the trail of a better solution. It is well known that any algorithm for this problem must require at least $n$ steps in the worst case.

Based on the information above, which of the following best describes what we know about the problem of smettlefying prime Jacobians?

1. It is in $\mathrm{\Theta }(n^3)$
2. It is in $\mathrm{\Theta }(n^2)$
3. It is in $\mathrm{\Theta }(n)$
4. It is in $O(n^3)$ and $\mathrm{\Omega }(n)$
5. It is in $\mathrm{\Omega }(n^3)$ and $O(n)$

¹Not a real problem.

Socrative Quiz

The following statements describe several different computational problems. For which of these problems will it be most worthwhile to search for a better algorithm?

1. Problem A is in $\mathrm{\Theta }(n^3)$
2. Problem B is in $\mathrm{\Theta }(n)$
3. Problem C is in $O(n^2)$ and $\mathrm{\Omega }(n)$
4. Problem D is in $O(n{2}^n)$ and $\mathrm{\Omega }(2^n)$
5. Problem E is in $O(\log n)$