Running time of algorithm A is at least O(n²) - Why is it meaningless?

Question

Why is the statement:

The running time of algorithm A is at least O(n²)

is meaningless ?

The running time of Insertion sort algorithm is at most O(n²)

Is it Correct?

I tried the net but could not get a good explanation.

I have another question:

I know that any linear function a⋅n+b is O(n) and also O(n²). Is it also O(n³)?

Answer 1

T(n): running time of Algo A. We just care about the upper bound and lower bound of T(n) The statement: T(n) >= O(n^2)

Upper bound: Because T(n) >= O(n^2), then there's no information about upper bound of T(n) Lower bound: Assume f(n) = O(n^2), then the statement: T(n) >= f(n), but f(n) could be anything that is "smaller" than n^2 , Ex: constant, n,..., So there's no conclusion about lower bound of T(n) too

=> The statement is meaningless

Answer 2

One reason could be that a lower bound without an upper bound isn't very useful. "at least" means it can be exponential in a normal case. If you don't know the upper bound you probably can't use the algorithm in a real application because you can't know if the program finishes before the universe does.

Big O notation when used properly indicates an upper bound. So stating a lower bound as big O is abusing the notation.

That said "meaningless" is a strong word. It's certainly useful information even if it isn't adequate. With a bit more context to your question you could get better help.

Answer 3

An analogy:

The statement is a bit like saying: "The roof of my house is at a height which is at least ground level." True, but completely uninformative.

Answer 4

O(n^2) is a worst-case scenario, meaning that the run time of A will be n^2 or faster. If its run-time is at least O(n^2) then that means the fastest run-time A can have, is at least O(n^2). This means that it could also be anything slower than O(n^2). These statements mean that A can have any possible run-time.