Big-O What are the constants k and n0 in the formal definition of the order of an algorithm?

Question

In my textbook I see the following:

Definition of the order of an algorithm

Algorithm A is order f(n) -- denoted O(f(n)) -- if constants k and n₀ exist such that A requires no more than k * f(n) time units to solve a problem of size n >= n₀.

---

I understand: Time requirements for different complexity classes grow at different rates. For instance, with increasing values of n, the time required for O(n) grows much more slowly than O(n²), which grows more slowly than O(n³), and so forth.

I do not understand: How k and n₀ fit into this definition.

1. What is n₀? Specifically, why does n have subscript 0, what does this subscript mean?

2. With question 1 answered, what does a 'a problem of size n >= n₀' mean? A larger data set? More loop repetitions? A growing problem size?

3. What is k then? Why is k being multiplied by f(n)? What does k have to do with increasing the problem size - n?

I've already looked at:

1. Big Oh Notation - formal definition

2. Constants in the formal definition of Big O

3. What is an easy way for finding C and N when proving the Big-Oh of an Algorithm?

4. Confused on how to find c and k for big O notation if f(x) = x^2+2x+1

Answer 1

1) n > n₀ - means that we agree that for small n A might need more than k*f(n) operations. Eg. bubble sort might be faster than quick sort or merge sort for very small inputs. Choice of 0 as a subscript is completely due to author preferences.

2) Larger input size.

3) k is a constant. Suppose one algorithm performs 1000*n operation for input of size n, so it is O(n). Another algorithm needs 5*n^2 operations for input of size n. That means for input of size 100, first algorithm needs 100,000 ops and the second one 50,000 ops. So, for input size about 100 you better choose the second one though it is quadratic, and the first one is linear. On the following picture you can see that n₀ = 200, because only with n greater than 200 quadratic function becomes more expensive than linear (here i assume that k equals 1).