Question

Justify the argument that an algorithm is efficient if its running time complexity can be expressed as a polynomial function of the problem size.

Answer 1

It is not easy to build an algorithm that takes time proportional to the size of the problem. For example, if the size of the array is n and you want to find a pair in the array such that the sum equals to the target value. It is difficult to create an algorithm that can do the task in time O(n) . The task can be easily done in time $O(n^2)$ by just checking the sum for each pair possible. But in order to do in O(n) time, it is not that easy. It can be done in O(n) time if the array is sorted by taking two pointers to the starting and ending of the array and then incrementing and decrementing the pointers accordingly till we get the required pair. It takes time O(n) with a condition that the array is sorted. But in a normal case, the array is not sorted. To sort, we need additional time and also the time O(n). Hence, the total time is which is greater than O(n) Hence, it is difficult to create such algorithms. So, if running time complexity can be expressed as a polynomial function of the problem size, then the algorithm is efficient.