How is O(N) algorithm also an O(N^2) algorithm?

Question

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?

Answer 1

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.

Answer 2

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.