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)\)