1

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.

Joe
  • 331
  • 1
  • 7
  • A close look at the definition https://en.wikipedia.org/wiki/Big_O_notation and examples should make things clear. – MrSmith42 Feb 02 '22 at 17:57

2 Answers2

3

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:

enter image description here

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

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

enter image description here

Here, we not only see that 0.2x2 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(x2), but also f(x) = O(x2).

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

slider
  • 12,810
  • 1
  • 26
  • 42
  • 1
    Thanks for your time and efforts : ) –  Feb 03 '22 at 17:32
  • so, can we say O(x) is the "tighter" upper-bound here which we usually consider. –  Feb 04 '22 at 08:28
  • 1
    @AnonCrack yes you can say that. It is "more precise" to describe the growth rate of *f(x)* here as *O(x)* instead of *O(x^2)*. – slider Feb 04 '22 at 18:48
2

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.

Joe
  • 331
  • 1
  • 7
  • 2
    Time complexity final exam tip: just write O(n^n!) for every answer and tell the prof that it's an upper bound. First date tip: when asked what you earn, say "I don't like to brag, but $10 billion is the upper bound of what I earn" – danh Feb 02 '22 at 18:03
  • @danh Thanks for the answers and if thats the case can i say O(1) can also be called as O(n!), if yes, its difficult to make any sense..kindly explain further..how is it allowed? –  Feb 02 '22 at 18:16
  • @joe, Thank you, so can we also say O(1) is same as O(n!) then.. if yes why..we have the concept of "upper-bound" here so how can we cross something that is called as upper-bound –  Feb 02 '22 at 18:21
  • @AnonCrack - I was wisecracking to illustrate that "upper bound" used in this way is misleading. The common way (only way?) to talk about upper bound is the *minimal upper bound*. I think the right answer to your question is to challenge the assertion that "O(n) algorithms can also be called as O(n^2)". That isn't the case under any definition I know of. – danh Feb 02 '22 at 18:27
  • @danh..please check this one where we say O(n) is also O(n^2) although its very unclear still https://stackoverflow.com/questions/44341669/how-is-on-algorithm-also-an-on2-algorithm#:~:text=O(n)%20is%20always%20O(n%5E2). –  Feb 02 '22 at 18:34
  • @danh: That’s not correct, although it’s easy to get that impression because people like to make useful correct statements rather than just technically correct statements. – Ry- Feb 02 '22 at 19:45
  • This answer is kind of right and definitely helpful, but O(n) time means that there is some factor c such that for all large enough n the function won't take more than cn time. Where the quantification of the multiple occurs in the statement is important, as is the "for large enough n". Ultimately, simplifying big-O away from a precise mathematical statement introduces this kind of small error and it's not useful (in my opinion) in the long-term to actually understanding what complexity is. – Paul Hankin Feb 03 '22 at 08:54