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³)?

Solution 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

Solution 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.

Solution 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.

Solution 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.

Solution 5

I know that any linear function an+b is O(n) and also O(n^2). Is it also O(n^3) ?

Yes, it is. The big-O notation denotes a whole collection of functions. But we should use it to characterize a function as closely as possible. While it is true that f(n) = an+b is O(n^2) or even O(n^3), it is more accurate to say that f(n) = O(n).

View more solutions

Comments

[tanmoy]

Thanks for your precise answer.If I consider A as Insertion sort algorithm,then is it useful to say "The running time of algorithm A is at least O(n2)?"in this context?

[tanmoy]

another doubt: Any linear function an+b is O(n) and also is O(n^2). Is it also O(n^3) ?

[Anders Forsgren]

Like I said, it is correct and meaningful to state the lower bound of the execution time, it is just that it is unusual to use big O notation for it, which is usually reserved for the upper bound of the time complexity. Saying "it is at least n2" is more formally described as (big) Omega(n^2), meaning "bounded below by n^2 asymptotically". So you should not use "O(..)" unless you mean "bounded above, asymptotycally". en.wikipedia.org/wiki/Big_O_notation

[tanmoy]

you said:"It's certainly useful information even if it isn't adequate" .so in which context it would be useful?

[Anders Forsgren]

For example it can be used to argue that it is a candidate for optimization or replacement ;€

[Soner from The Ottoman Empire]

that's nice to grasp its idea +1