Analyzing Problems

Socrative Quiz

Professor Arugorizumu has been studying the computational problem of smettlefying prime Jacobians¹. He has published a clever $\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 $\Theta(n^3)$
2. It is in $\Theta(n^2)$
3. It is in $\Theta(n)$
4. It is in $O(n^3)$ and $\Omega(n)$
5. It is in $\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 $\Theta(n^3)$
2. Problem B is in $\Theta(n)$
3. Problem C is in $O(n^2)$ and $\Omega(n)$
4. Problem D is in $O(n 2^n)$ and $\Omega(2^n)$
5. Problem E is in $O(\log n)$