Why the statement, “The running time of this algorithm is O(n^2) or worse,” can not provide any information about algorithm?

1 Answer

sciencesolve's profile pic

sciencesolve | Teacher | (Level 3) Educator Emeritus

Posted on

The statement "`O(n^2)` or worse" shows that the time is superior bounded by any function that is larger or equal to the size of input, that is n^2.

Since the running time `O(n^2)` estimates how much an algorithm increases, thus it estimates its efficiency and hence the statement provided by the problem, "`O(n^2)` or worse" is valid for any function that has the property to be larger than `n^2` , which means all functions, then it is impossible to perform the running time analysis.

Hence, as a conclusion, the given statement "the running time of this algorithm is `O(n^2)` or worse" cannot be considered as valuable in making valid estimations concerning the algorithm whose input is `n^2` .