1

Suppose we have a function, f(n)=n+10. We say that f(n)∈O(n), meaning O(n) represents the upper bound of the function.

It is also true that f(n)∈O(n2) or f(n)∈O(n3) and so on.

So how can we say that O(n) is the upper bound when O(n2) is comparatively bigger bound and O(n3) is much bigger bound?

Please forgive if I have understood the concept wrongly.

logc
  • 2,190
  • 15
  • 19
user3652549
  • 19
  • 1
  • 2
  • I somehow could not get an answer through the link you provided. I would really appreciate if you could explain the answer to my question. Thank you in advance. – user3652549 Jan 10 '15 at 19:48
  • Please follow the former given link to: http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o – thepacker Jan 10 '15 at 19:53
  • 1
    The least upper bound on that function is O(1). –  Jan 11 '15 at 05:45
  • 1
    @Snowman: No, the least upper bound on `f(n)=n+10` is `O(n)` (i.e., the upper+lower bound, i.e. `f(n) ∈ Θ(n)`). Big O notation defined as being applied to functions, not execution times. – Brian Jan 12 '15 at 14:16

2 Answers2

15

It is very easy to eliminate your confusion because it comes from a single word:

O(n) represents the upper bound of the function.

That's incorrect. The correct statement is:

O(n) represents an upper bound of the function.

Big-O notation does not mean that the function named in the notation is the least upper bound, just that it is an upper bound.

When we rewrite your question as:

How can we say that O(n) is an upper bound when O(n2) is comparatively bigger bound and O(n3) is much bigger bound?

the question becomes clear. There are no humans taller than 100 meters tall; that's an upper bound on human height. 200 meters and 10000000 meters are also upper bounds; the existence of larger upper bounds does not mean that a smaller upper bound is not also an upper bound. None of these are the least upper bound.

Now, in your example O(n) happens to be the least upper bound on the function you give. There are also larger upper bounds, as you note, and therefore those are not the least upper bounds.

Eric Lippert
  • 45,799
  • 22
  • 87
  • 126
  • 1
    +1 for addressing only the one detail of Big-O that OP was confused about: The non-uniqueness of upper bounds. As a slight improvement, it'd be nice to see an explicit contrast of "upper bound" with "maximum", since OP may have assumed those are synonymous. – Ixrec Jan 10 '15 at 21:52
  • Actually, the *least* upper bound on `f(x)=x+10` is O(1), as the execution time of the function is independent of the value of `x`. – Bart van Ingen Schenau Jan 12 '15 at 08:35
  • @BartvanIngenSchenau: That is incorrect. O(1) is defined as being applied to functions, not execution times. – Brian Jan 12 '15 at 14:10
  • 1
    @Brian: Perhaps we use different interpretations of the term "function" here. The function that calculates the value of `x+10` has constant complexity (O(1)). An algorithm whose complexity is described by the function `n+10` has linear complexity (O(n)). When talking about algorithm/function complexity, the default is how it scales in time (i.e. execution time), although space complexity is also possible. – Bart van Ingen Schenau Jan 12 '15 at 14:20
  • @Brian: I see your point. I interpreted the question as being "I have a program whose cost is `f(n) = n + 10`, which is `O(n)`. I think you are interpreting the question as "I have the program fragment `(int n) => n + 10`, which I agree is `O(1)`. – Eric Lippert Jan 12 '15 at 17:15
1

f(n) = O(g(n)) states that if there exists some constant c>0 and n0>0, then f(n) <= cg(n) for all n >= n0. Here n0 is a limit above which we consider n i.e. we try to find asymptotic notation that itself means that we want to find time complexity for large values of n. So, we consider n0 as lower limit of n and above n0 this statement holds.

So, you have misunderstood that O(g(n)) with O(n), if we have two function with time complexity f(n1) = O(n1) and f(n2)= O(n22) then there is a property of Big-O which is O(resulting function) = max(O(n1),O(n22)). So, by this in this case O(n2) is upper bound in comparison to O(n).

logc
  • 2,190
  • 15
  • 19
lifecodemohit
  • 11
  • 1