Let P be a problem. The worst-case time complexity of P is O (n^2). The worst-ca
ID: 3889202 • Letter: L
Question
Let P be a problem. The worst-case time complexity of P is O (n^2). The worst-case time complexity of P is also Ohm (n log n). Let A be an algorithm that solves P. Which subset of the following statements are consistent with this information about the complexity of P? Justify your answer. (a) A has worst-case time complexity O (n^2). (b) A has worst-case time complexity O (n^3/2) (c) A has worst-case time complexity O (n). (d) A has worst-case time complexity theta (n^2). (e) A has worst-case time complexity theta (n^3).Explanation / Answer
The big Oh complexity determines the upper bound of the complexity while the big-Omega complexity determines the lower bound of the complexity.. Hence the complexity must be between n^2 and nlong(n).
a) Complexity O(n^2) : Correct.. As the upper bound is o(n^2)
b) n^3/2 is lesser than n^2, and hence we can not surely say that it will be upper bound, because real complexity may be more than n^3/2. Hence incorrect
c) Again n is lesser than n^2, Hence incorrect.
d) incorrect, This is a theta notation which means upper and lower bound both will be in between order of n^2 for some constants such as k*n^2 < T(n) < C * n^2.
Now as we know our lower bound is nLog(n) which itself is lesser than n^2., hence upper bound and lower bound can not be restricted between complexity of n^2.
e) incorrect, similar as above.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.