Question

In one or 2 sentences, explain the difference between upper bound of the time complexity of a problem and upper bound on the time complexity of an algorithm to solve that problem.

Answer 1

Which so ever the bound it may be , most of the time the worst case input is only taken into consideration . So, while taking the case of sorting , it can be assumed that the worst case is an unsorted input list .

Now as per the question the problems tend to have a lower bound. For example , it is known that the lower bound of the comparison based sorting is Ω (nlogn), here in this case no assumptions regarding the particular type of comparison sorting algorithm that has been employed .Which so ever the algorithm it may be ( quick, merge , bubble ,etc.) the bound cannot be better than then Ω (nlogn) . Thus in general terms the lower bound tells of the time complexity of a problem and how hard is the problem .

Whereas in case of an algorithm , the upper bounds are taken into consideration .for example ,in case of bubble sorrt th eupper bound will be O(n^2) , while in case of merge sort the upper bound is O(nlogn) . Hence , the upper bounds tells the time complexity of the algorithm and how much efficient the algorithm is in solving problems .