9

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

tanmoy
  • 1,373
  • 3
  • 20
  • 31
  • 1
    In what context do you ask this question? – nhahtdh Mar 04 '13 at 06:47
  • 4
    It's meaningless because you haven't provided any Algorithm A. – aqua Mar 04 '13 at 06:51
  • Let algorithm A is insertion sort algorithm. – tanmoy Mar 04 '13 at 06:53
  • 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
  • 1
    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

10 Answers10

15

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

CuberChase
  • 4,380
  • 5
  • 32
  • 52
Cao Minh Vu
  • 1,800
  • 1
  • 14
  • 20
8

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.

Anders Forsgren
  • 10,408
  • 4
  • 37
  • 74
  • 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 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 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 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
2

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.

Aky
  • 1,767
  • 1
  • 14
  • 18
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.

Dehli
  • 5,850
  • 5
  • 28
  • 42
1

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

Eugene Yarmash
  • 131,677
  • 37
  • 301
  • 358
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

Simplex
  • 1,693
  • 1
  • 17
  • 26
0

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

Grigor Gevorgyan
  • 6,595
  • 4
  • 33
  • 63
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.

artahian
  • 2,045
  • 13
  • 16
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.

Rubens
  • 13,978
  • 10
  • 59
  • 92
Hemant
  • 1
-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.

lacungus
  • 77
  • 4