Search code examples
algorithmbig-ocomplexity-theory

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

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?

Solution

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