Explain why the statement, “The running time of algorithm A is at least ,” is meaningless.
Let us assume the running time of the algorithm is . Now, by definition, -notation gives an upper bound for growth of functions but it doesn’t specifies the order of growth. Therefore, saying means growth of 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, is for all . So, doesn’t tell us anything new as all running times are non-negative.