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

It's meaningless because you haven't provided any Algorithm A. — aqua, Mar 04 '13 at 06:51
The `Big Oh` notation provides an upper bound on the running time of the algorithm (**worst-case** scenario). It is certainly **not** meaningless! In addition, the analysis of the worst case complexity is easier in most case as compared with the average case analysis of an algorithm. [A Plain English explanation of Big O](http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) — Devendra D. Chavan, Mar 04 '13 at 06:57
I interpreted o(n^2) "at least" as a running time that wasn't a worse case, that is not a proper big O in this context. — Anders Forsgren, Mar 04 '13 at 07:02

score 15 · Accepted Answer · edited Mar 16 '13 at 04:53

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

Anders Forsgren · Answer 2 · 2013-03-04T07:04:21.280

9

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.

edited Mar 04 '13 at 07:04

answered Mar 04 '13 at 06:56

Anders Forsgren

10,827
4
40
77

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 Banerjee Mar 06 '13 at 15:53
another doubt: Any linear function an+b is O(n) and also is O(n^2). Is it also O(n^3) ? – Tanmoy Banerjee Mar 06 '13 at 16:02
1

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". http://en.wikipedia.org/wiki/Big_O_notation – Anders Forsgren Mar 06 '13 at 16:04
you said:"It's certainly useful information even if it isn't adequate" .so in which context it would be useful? – Tanmoy Banerjee Mar 06 '13 at 16:08
For example it can be used to argue that it is a candidate for optimization or replacement ;€ – Anders Forsgren Mar 06 '13 at 18:40

score 4 · Answer 3 · answered Jan 14 '18 at 07:05

4

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.

answered Jan 14 '18 at 07:05

Aky

1,777
1
14
19

that's nice to grasp its idea +1 – Soner from The Ottoman Empire Oct 17 '18 at 14:25

Dehli · Answer 4 · 2013-09-17T16:35:23.033

1

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.

edited Sep 17 '13 at 16:35

answered Sep 16 '13 at 22:34

Dehli

5,950
5
29
44

score 1 · Answer 5 · answered Jan 06 '14 at 23:46

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

score 0 · Answer 6 · answered Mar 04 '13 at 07:26

0

O-notation, in other words means: f(x) belongs set O(g(x)) if f(x) < C * g(x), for all C (those are Real Numbers)

i.e. your algorithm does not grow more than a quadratic function

answered Mar 04 '13 at 07:26

Simplex

1,723
2
17
26

score 0 · Answer 7 · answered Mar 04 '13 at 09:37

It's not meaningless, it can be used for example if you don't know the exact algorithm, but you certainly know that it will require O(n^2) operations.

For example, if one doesn't know about sorting algorithms, but understands, that to sort an array we need at least to look at every element, one can say that "sorting an array is at least O(n)".

score 0 · Answer 8 · answered Mar 04 '13 at 15:54

0

Because no one cares how fast it works in best case, the worst case is important. Usually people are interested to know how much it will take in worst case.

answered Mar 04 '13 at 15:54

artahian

2,093
14
17

score 0 · Answer 9 · edited Aug 04 '13 at 15:21

0

Let f(n) be the running time of the algorithm.

=> f(n) >= O(n2)
=> f(n) >= 0 , because 0 is a member of set of functions that are O(n2)

This is always true for f(n), since running time is always non negative. Hence, the statement is redundant.

edited Aug 04 '13 at 15:21

Rubens

14,478
11
63
92

answered Aug 04 '13 at 15:04

Hemant

1

Maadesh Sivakumar · Answer 10 · 2022-10-19T19:00:00.233

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

Let's assume the runtime of algorithm A

T(n) = O(log n)

From this we already have

T(n) <= c.log n

What the statement tries to say by at least O(n²) is that

T(n) <= c.n²
=> c.log n <= c.n²   #for some c>0 and n>=n0

Which is quite obvious. When we already know T(n) <= c.logn , saying T(n) <= c.n2 does not add value.

So, when we already have a lower or upper bound of an algorithm, to say that the bound is at least or at most (respectively) never adds any new information that we already do not know.

To answer your second question

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

Yes. By definition of upper bound (big-O) it just means that

a.n+b <= c.n

So, if this is true then this is also true

a.n+b <= c.n³

score -3 · Answer 11 · answered Mar 04 '13 at 07:16

-3

"The running time of algorithm A is at least O(n2)" is equivalent to "The running time of algorithm A is Big Omega(n2)", so it's not meaningless.

answered Mar 04 '13 at 07:16

lacungus

77
4

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

11 Answers11