What is meant with finding real and integer constants in Big Oh notation?

Question

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.

Answer 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.

Answer 2

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/J₀(n) + eⁿ? The formal mathematical definition gives you a way of unambiguously working out Big O for any function.