Which of the following is the most precise classification of a problem X?

Question

Which of the following is the most precise classification of a problem X?

• X is in NP
• X is in P
• X is in O(n²)
• X is in Θ(n²).

I would greatly appreciate if anyone could explain the answer of this to me?

I believe it's either NP or P, but i'm really not sure

Answer 1

NP or P means whether it can be solved in polynomial time in a non deterministic machine(NP) or in a deterministic machine(P). This reflects the complexity of the problem but not the complexity of an algorithm that solves the problem.

While O(n^2) means that the algorithm being analyzed to solve a problem has an upper bound of n^2 complexity when n is the input.

Theta(n^2) is also a way of expressing the complexity of an algorithm used to solve a problem but Theta(n^2) in contrast of O(n^2) means that that the lower and upper bound of complexity is n^2.

There's also another measure which is o(little-oh) which indicates the lower bound complexity of an algorithm.

Theta is more precise because like O(n^2) means just upper bound, the algorithm is also O(n^3) and O(n!).

Answer 2

Θ(n²) ⊂ O(n²) ⊂ P ⊆ NP