I'm a beginner in algorithms and trying to understand time-complexity and read online that any algorithm whose time-complexity is O(n) is the upper-bound which means there is no way that the time-taken by that particular algorithm could be expressed above O(n).

but understood that O(n) algorithms can also be called as O(n^2)(If so, then why do we call "O(n) as the upper-bound" and also we say Big-O gives upper bound ? ). How is it possible technically ? can someone explain for the beginners.

Note: Kindly do not mark as duplicate, we are unable to understand from the mathematical relations and other examples available.

Thanks in advance.

CodePudding user response：

If an algorithm is described as being "in O(n) time", then it will never take longer than some multiple of its size, in time, to run.

Every algorithm that is O(n) is also O(n^2), and O(n^3), and O(2^n) - in the same way that every number smaller than 3 is also smaller than 5, and 7, and 1,000.

CodePudding user response：

Maybe it is better explained through pictures. However, you will have to try to understand the mathematical definition of Big O.

A function f is Big O of another function g, or f(x) = O(g(x)), if we can find a point on the x-axis so that after that point, some "stretched version" of g(x) (like 3g(x) or 5g(x)) is always greater than f(x).

So g(x) is like a "measuring function" which tries to give you a feel for how fast f grows. What does this mean with pictures?

Suppose f is the function 2x 3sin(x) 10. Then, in the following picture, we see that a stretched version of g(x) = x (specifically, 4g(x)) is above f after x = 3.933:

Therefore, we can say that our chosen function f is O(x).

Now let's add another function k(x) = x² into the mix. Let's take its stretched version 0.2x² and plot it:

Here, we not only see that 0.2x² is greater than 4x after some point, it is also greater than f(x) (much earlier, in fact). So we can say that 4x = O(x²), but also f(x) = O(x²).

You can play around with the graphs here: https://www.desmos.com/calculator/okeagehzbh