The precise time complexity of which of the following problems has not yet been established by researchers?
A) Sorting a list
B) Searching through a list for a particular entry
C) The traveling salesman problem
D) Listing all possible subcommittees within a given committee

Question

Quizplus · Accepted Answer

The precise time complexity of the traveling salesman problem has not yet been established by researchers. The best known algorithm for solving the problem has a worst-case time complexity of O(2^n * n^2), but it is not known whether a better algorithm exists. The time complexity of sorting a list is O(n log n), searching through a list for a particular entry is O(n), and listing all possible subcommittees within a given committee is also O(2^n).

The Precise Time Complexity of Which of the Following Problems