Explain why the statement, “The running time of algorithm \(A\) is at least \(O(n^2)\),” is meaningless.
Let us assume the running time of the algorithm is \(T(n)\). Now, by definition, \(O\)-notation gives an upper bound for growth of functions but it doesn’t specify the order of growth.
Therefore, saying \(T(n) \ge O(n^2)\) means growth of \(T(n)\) is greater than some upper bound which is meaningless as we do not have any idea about what we are comparing it with.
For example, \(f(n) = 0\) is \(O(n^2)\) for all \(n\). So, \(T(n) \ge f(n)\) doesn’t tell us anything new as all running times are non-negative.