Big-O when the value of n gets very small?

Question

I missed the class where big-O was introduced thinking that it was pretty straight forward. It still seems to be however the teacher said something about O(n) deviating from the function when n gets very small? I couldn't find this anywhere in the book. Could someone enlighten me? Our exploration of O(n) has been in the context of sorting algorithms if that is of any significance.

Thanks Gene

edit: Thanks for the help guys it has been illuminating. I have a follow-up question. Is there a relatively simple mathematical way to figure out the point where n is too small for O(n)?

Related questions

are there any O(1/n) algorithms?
What is the difference between Θ(n) and O(n)?

Answer 1

Big O doesn't describe the execution time of a function, just the growth. All functions have some constant factor or overhead that needs to be added in. When n is low, this overhead can greatly dwarf any improvements to the algorithm - an algorithm that requires 50ms per operation but has O(n) will perform worse for small n than an algorithm that requires 5 ms per operation, but has O(n*n).

This is why, in general, for small sets big O doesn't matter. For most objects with simple comparisons, a quick sort on 10 items will not be noticiably faster than a bubble sort, a linear search on 100 items will probably be faster than a binary tree, and so on.

Answer 2

The course material gets harder to understand as the number of lectures attended (N) becomes very small.

Answer 3

Maybe the following is an example of "O(n) deviating from the function when n gets very small":

Consider an operation which requires, for example, time "50 times n, plus n squared".

When n is large then the "n squared" term will dominate, and so the operation can be said to be "O(n squared)".

When n is small, however, the "n squared" term will be negligible, and the "50 times n" term will dominate, and so when (and only when) n is small then it could be said to be O(n).

Answer 4

To expand on the answer above, Big-Oh notation measures the eventual growth of the function or its limiting behavior.

f = O(g) if and only there exists an N and a constant c (which can be a function of N) such that for all n > N,
f(n) <= c*g(n)

Lets say f = 10000000*n and g = n^2.

f = O(g), however if you look at too small values of n, say less than 10000000 and set c = 1, you will see that g(n) <= f(n).

---

To add a more extreme example, would you rather deal with an algorithm with complexity n^100000 or an algorithm with complexity of 2^(.0000000001n). For reasonable problem sizes, the latter is better. What makes a lot of CS so beautiful is that it allows for this type of abuse, however, most natural algorithms do not take advantage of it. Most polynomial time algorithms have small constants (at least after a little of work).

Good luck!

Answer 5

The concept behind Big-O notation is the asymptotic performance of the algorithm. As N gets bigger, the term in the Big-O notation comes to dominate the total time. For example, in an O(N^2) algorithm, the total time T(N) might be:

T(N) = a * N * N + b * N + c

As N gets bigger, and bigger, the term in N^2 dominates, regardless of the value of b or c.

When N is small, though, the b and c terms matter.

For example, if a = 0.001, b = 1,000, and c = 1,000,000.

 N                ~ T(N) [1 significant figure]
 1                1,000,000                (almost all c)
 1,000            2,000,000                (50:50 split on b and c)
 1,000,000        2,000,000,000            (50:50 split on a and b)
 1,000,000,000    1,000,000,000,000,000    (almost all a)

So, if you ignored the low-order terms, the performance at low N would be completely misrepresented. At high N, the low-order terms don't matter.

Answer 6

A big off topic but for the sake of completeness I want to mention some other notations which are related to the Big_o notation and commonly used in theoretical computer science and which you may find referred to in computer science literature: The Big-Θ notation, the Big-Ω notation and the little-o notation. These are simply other (and tighter) descriptions of growth rates. The little-o notation is easily mistaken for the big-O notation.

The little-o is also a relation between two functions f(x) and g(x). Saying that 'f(x) is little-o of g(x)' means that f(x) grows much faster than g(x). In more mathematical tearms is says that the limit of f(x)/g(x) is zero, as x approaches infinity.

As mentioned in the previous answers the big-O notation is used to describe the upper bound of the growth rate of an algorithm. It is really a relation between two functions f(x) and g(x), where f(x) = O(g(x)) as x goes to infinity.

See the Big-o wikipedia page for a nice and concise presentation of the different notations.

Answer 7

According to the definition:
f(n)=Θ(g(n)) means the set of all the functions f(n) such that there needs to be constants c1 and c2 and also n0 where all of these cases are true:

• c1 . g(n) is a non-negative term or 0.
• c1 . g(n) <= f(n) [g(n) needs to be the lower bound for certain n]
• f(n) <= c2 . g(n) [g(n) needs to be the upper bound too since we are defining Θ].
• for all n greater than our selected n0

So all we need to do is select such a c1, c2 and n0 that makes ALL the conditions true. Therefore for certain combinations of c1 c2, if you select n < n0, you cannot guarantee that your bound works. I think this is what your teacher meant by "the deviation".