7

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 n0 exist such that A requires no more than k * f(n) time units to solve a problem of size n >= n0.

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(n2), which grows more slowly than O(n3), and so forth.

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

  1. What is n0? 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 >= n0' 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

Community
  • 1
  • 1
Estex
  • 93
  • 1
  • 7

3 Answers3

7

1) n > n0 - 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 n0 = 200, because only with n greater than 200 quadratic function becomes more expensive than linear (here i assume that k equals 1).

enter image description here

Yola
  • 18,496
  • 11
  • 65
  • 106
  • So how do you determine if these constants exist whether by analyzing the algorithm or by looking at an equation? – Estex Mar 07 '18 at 05:11
  • 2
    @Estex You need to look at an algorithm implementation and just count operations. Suppose you have linear complexity algorithm, so you count number of operation on every loop iteration and that is your *k*. – Yola Mar 07 '18 at 05:20
  • Ok well there's a connection I needed. But what about n0? – Estex Mar 07 '18 at 05:26
  • @Estex i updated the answer with a picture, hope it helps. – Yola Mar 07 '18 at 05:50
  • 2
    Note that precisely computing a `k` in general is *not feasible*. If you would break it all the way down you would need to count the number of machine instructions. And some statement might trigger multiple instructions internally, you don't know in general. But it does not really matter since the definition allows an arbitrary big `k` as long as it is a constant. So in an analysis you would just leave it as abstract `k`, not specifying a specific number. And sometimes you would need to increase it, for example if the other side has `2k` you would need an `a > 2k` (which exists of course). – Zabuzard Mar 07 '18 at 16:29
  • 2
    Same holds for an `n0`. You can easily compute numbers if you compare ordinary functions, but not with algorithms. You first need to abstract the algorithm into some kind of function and this often involves just counting the iterations in dependency to the input size, like `27n^2 + 3n` iterations. This function then, using Big-O definition, yields `O(n^2)`. Finding the numbers is now easy, you choose `k = 28` and receive `28n^2 > 27n^2 + 3n`. But this equation doesn't hold for all `n`, you would need to find the `n_0` such that it starts holding for `n > n_0`. For example for `n_0 = 10`. – Zabuzard Mar 07 '18 at 16:33
  • 1
    Or you choose `k = 100`, then it will probably hold for all `n`, so `n_0 = 1` is fine. So you don't need to determine `k` and `n_0` that precise that lower numbers won't work. Any combination for which it holds it fine, you may select arbitrary big numbers. – Zabuzard Mar 07 '18 at 16:34
  • 1
    @Zabuza agree, here i provided this computation to show the principle, however computation of k and n0 in real system maybe complicated and we usually agree on some level of abstraction. – Yola Mar 07 '18 at 16:38
  • Ok... So the purpose of Big-O is to distinguish *significant* differences between algorithms, k corresponds to the maximum number of timed operations contained in an algorithm (y value on the graph of function f(n)), n corresponds to the input size (x value on the graph of function f(n)), and n0 corresponds to input sizes large enough to prove that the max time to complete an algorithm is k*f(n)? – Estex Mar 12 '18 at 20:15
  • @Estex yes, you got it right! You can try find another combinations of `k` and `n0` which work. – Yola Mar 13 '18 at 05:46
  • @Estex your description of k was helpful. With n0: Are you specifying a constant n0, such that n ≥ n0 will allow you to define an upper bound with O(n)? I'm still confused because this doesn't really do anything for me when n appears on both sides of f(n) ∈ O(g(n)). – Steve3p0 Apr 08 '21 at 14:31
  • I understand n0 now after reading the other answers . – Steve3p0 Apr 08 '21 at 14:43
3

n is the problem size, however that is best measured. Thus n0 is a specific constant n, specifically the threshold after which the relationship holds. The specific value is irrelevant for big-oh, being only interested in its existence.

k is also an arbitrary constant, whose bare existence (in conjunction with n0) is important for big-oh.

Naturally, people are also interested in smaller problems, and in fact the perfect algorithm for a big problem might be decidedly inefficient for a small one, due to the constants involved.

Deduplicator
  • 44,692
  • 7
  • 66
  • 118
2
  1. It means the first value for n for which the rest holds true (i.e. we're only interested in high enough values for n)
  2. Problem size, usually the size of the input.
  3. It means you don't care about the different (for example) between 3*n^2 and 400*n^2, so any value that is high enough to satisfy the equation is OK.

All of these conditions aim to simplify the O notation, making the difference between simple and complex operations mute (e.g. you don't care if an operation is one or 20 cycles as long as the number is finite).

Ofir
  • 8,194
  • 2
  • 29
  • 44