14

I was reading about Big-O Notation

So, any algorithm that is O(N) is also an O(N^2).

It seems confusing to me, I know that Big-O gives upper bound only.

But how can an O(N) algorithm also be an O(N^2) algorithm.

Is there any examples where it is the case?

I can't think of any.

Can anyone explain it to me?

Nadir Laskar
  • 4,012
  • 2
  • 16
  • 33
  • 2
    If an algorithm is upper bounded by `N`, then it follows that it must also be upper bounded by `N^2`, which is a much higher bound. But typically we would not report something as `O(N^2)` if we could give it a tighter bound of `O(N)`. – Tim Biegeleisen Jun 03 '17 at 07:49
  • 7
    `x < 5` also means `x < 25`. – ayhan Jun 03 '17 at 07:50
  • 1
    Please, check this thread: https://stackoverflow.com/questions/22594174/can-an-on-algorithm-ever-exceed-on2-in-terms-of-computation-time. It may be helpful in your research. – eg04lt3r Jun 03 '17 at 07:55
  • 1
    @TimBiegeleisen Actually, you would report something as O(N^2) even if it is actually O(N) because, for example, O(N^2) is good enough and proving it is O(N) is much harder. – Makogan Feb 07 '19 at 17:50

6 Answers6

10

"Upper bound" means the algorithm takes no longer than (i.e. <=) that long (as the input size tends to infinity, with relevant constant factors considered).

It does not mean it will ever actually take that long.

Something that's O(n) is also O(n log n), O(n2), O(n3), O(2n) and also anything else that's asymptotically bigger than n.

If you're comfortable with the relevant mathematics, you can also see this from the formal definition.

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
  • Thanks, for the comment. But don't we try to be more precise here with Big-O. Are there any examples where O(N) can be O(N^2)? – Nadir Laskar Jun 03 '17 at 08:15
  • @NadirLaskar O(N) is always O(N^2), you are thinking in terms of tight bound – perreal Jun 03 '17 at 08:20
  • 1
    @NadirLaskar No, big-O is only an upper bound, which means what I described in the answer. O(n) is **always** O(n^2). Big-Theta (Θ) would be what you're looking for if you want a tight (lower >= and upper <=) bound. An algorithm that's sometimes Θ(n) and sometimes Θ(n^2) have to do with the best, average and worst cases of the algorithm (each of which has it's own complexity), and is an entirely different question than what big-O actually means and what was said in that quote. – Bernhard Barker Jun 03 '17 at 08:23
  • Cool! So basically, every algorithm I ever wrote was O(n!). At least I really hope so :D – Eric Duminil May 03 '23 at 12:00
6

O notation can be naively read as "less than".

In numbers if I tell you x < 4 well then obviously x<5 and x< 6 and so on.

O(n) means that, if the input size of an algorithm is n (n could be the number of elements, or the size of an element or anything else that mathematically describes the size of the input) then the algorithm runs "about n iterations".

More formally it means that the number of steps x in the algorithm satisfies that:

x < k*n + C where K and C are real positive numbers

In other words, for all possible inputs, if the size of the input is n, then the algorithm executes no more than k*n + C steps.

O(n^2) is similar except the bound is kn^2 + C. Since n is a natural number n^2 >= n so the definition still holds. It is true that, because x < kn + C then x < k*n^2 + C.

So an O(n) algorithm is an O(n^2) algorithm, and an O(N^3 algorithm) and an O(n^n) algorithm and so on.

Makogan
  • 8,208
  • 7
  • 44
  • 112
2

Big-O notation describes the upper bound, but it is not wrong to say that O(n) is also O(n^2). O(n) alghoritms are subset of O(n^2) alghoritms. It's the same that squares are subsets of all rectangles, but not every rectangle is a square. So technically it is correct to say that O(n) alghoritm is O(n^2) alghoritm even if it is not precise.

dey
  • 3,022
  • 1
  • 15
  • 25
2

For something to be O(N), it means that for large N, it is less than the function f(N)=k*N for some fixed k. But it's also less than k*N^2. So O(N) implies O(N^2), or more generally, O(N^m) for all m>1.

*I assumed that N>=1, which is indeed the case for large N.

Ken Wei
  • 3,020
  • 1
  • 10
  • 30
1

Definition of big-O:

Some function f(x) is O(g(x)) iff |f(x)| <= M|g(x)| for all x >= x0.

Clearly if g1(x) <= g2(x) then |f(x)| <= M|g1(x)| <= M|g2(x)|.

Yola
  • 18,496
  • 11
  • 65
  • 106
-1

For an algorithm with just a single Loop will get a O(n) and algorithm with a nested loop will get a O(n^2). Now consider the Bubble sort algorithm it uses the nested loop in it,

If we give an already sort set of inputs to a bubble sort algorithm the inner loop will never get executed so for a scenario like this it gets O(n) and for the other cases it gets O(n^2).

Praveen Kumar Karthikeyan
  • 29
  • 8
  • That's not what the quoted statement is about. Since O(...) only talks about an upper bound (i.e. a value that's known to be bigger than something else) putting something that's "too big" inside the parenthesis is always correct (but less useful). – Joachim Sauer Mar 09 '22 at 09:08