0

From my book "Data Structures & Algorithms in Java: Sixth Edition" the definition of Big Oh is the following:

Let f(n) and g(n) be functions mapping positive integers to positive real numbers. We say that f(n) is O(g(n)) if there is a real constant c > 0 and an integer constant n0 >= 1 such that f(n) <= c * g(n) for n >= 0

They then show that the function 8n + 5 is O(n) and use the following justification:

By the big-Oh definition, we need to find a real constant c > 0 and integer constant n0 >= 1 such that 8n+5 <= c * n for every integer n >= n0. It is easy to see that a possible choice is c = 9 and n0 = 5. Indeed, this is one of infinitely many choices available because there is a trade-off between cd and n0. For example, we could rely on constant c = 13 and n0 = 1

In my bachelor's studies, I learned that big O is just the largest increasing factor in a method f(n) and as such this description is new to me. I can answer the questions by finding the biggest factor, but cannot justify. It would help me if I knew:

  • What is meant with "a real constant c > 0" and "an integer constant n0 >= 1" What do these mean?

  • What trade-off is being talked about when they say there is a tradeoff between c and n0?

  • Why does the choice of c and n0 matter? It feels strange picking arbitrary values like c = 9999999999 and n0=1 and then concluding that indeed f(n) is Big-Oh of O(g(n)) just because 8*1 + 5 <= 999999999* 1

I can't imagine a case where a function f(n) would be bigger than c*n if you're free in choosing the c.

Improve this question
1
  • The point is you're not choosing c or n0 ... you're asking whether or not any possible pair of c and n0 exists that can satisfy the constraints given. Commented Jan 28, 2018 at 10:05

2 Answers 2

Reset to default
1

I'll try to help you build some intuition about this. So, to start with, the notion is expressed in terms of functions that map positive integers to positive real numbers. Since the context is computer science, you can probably guess that this is because it's a representation of how a discrete variable, the size of the input (an integer, n), maps to execution time, which is a real number. Note that in the real world, there are many factors that can affect the execution time in various ways, so in general, it will not be some "nice" function. But in analysis, we make some assumptions that allow us to create a good enough estimate, something we can work with (e.g., we have this notion of elementary operations that take a fixed amount of time, and we assume that we can simply count them, and ignore other subtleties).

Next, what's the significance of the real constant c, and the integer n0? The constant c is just a multiplier. We are interested in classifying algorithms by their growth into a relatively small number of categories, so, for example, if something grows at most linearly (proportional to n), we don't really care if it's 0.5*n or 10*n or 20.125*n (or c*n) - we treat it all as the same time complexity. If you look at the graph of c*n, the constant c just scales it vertically, so that for some value of c, c*n is always >= f(n) for large values of n (that is, it bounds f(n) it from above).

What about n0? In general, we want to know how the algorithm behaves for large values of n. For some initial, finite range of values that n can take, the value of f(n) (the execution time), may exceed the corresponding value of g(n). Intuitively, this is because for lower values of n, there's an interplay between various factors that contribute to the execution time, so we can't really tell what is going on. But as n grows, one of them becomes dominant, and things become more clear (i.e., one term in the function f(x) begins to grow more rapidly than all the others - which is why we can ignore them, BTW). This means that we can find some n = n0 after which f(n) <= c*g(n) is always true (the actual value of n0 doesn't matter, just that it exists).

This is what Figure 4.5 depicts. You may also want to (re?)read the discussion just under Example 4.6.

Improve this answer
5

The difference here is between your informal definition ("the largest increasing factor") and a rigorous mathematical definition of O(n). How do you know that "the largest increasing factor" in (n + log n) is n rather than log n?

You may have a little cribsheet of rules you use so that you can look at a simple set of factors (I'm guessing polynomials, logarithms, exponentials and maybe factorials), but what are you going to do when you get something you don't know about like a Bessel function? What's Big O for 1/J0(n) + en? The formal mathematical definition gives you a way of unambiguously working out Big O for any function.

Improve this answer
4
  • Thank you, I was suspecting myself of this too. And indeed, it was these simple set of factors. However, I don't think I understand the mathematical notation of Big O then, which was one of the questions in my OP. Could you perhaps elaborate on those other questions a bit more? As a side note.. That Bessel function.. Besselled me. Commented Jan 27, 2018 at 19:37
  • 3
    @Zimano: He's saying that all of your questions are part of a more rigorous mathematical formalism, and that your path forward is to learn that formalism. Commented Jan 27, 2018 at 19:50
  • I think so too. And while I value the mathematical formalism,I specifically noted the things I do not understand about the problem. My path forward in the short run is to understand the current problem at hand, hence why I asked the question. As it currently stands the answer does not answer my question; it reinforces what I already suspected: My bachelor's method is not sufficient. I am at this moment learning the mathematical formalism and asked this question because these are the parts I don't understand about it. Commented Jan 27, 2018 at 21:09
  • Then perhaps your question might be better served at math.stackexchange.com Commented Jan 28, 2018 at 0:32

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.