CODEWITHSUNDEEP
algorithmperformancebig-onotation
Estex
Estex

Reputation: 93

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

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

Upvotes: 7

Views: 4715

Answers (3)

Yola
Yola

Reputation: 19041

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

Upvotes: 7

Deduplicator
Deduplicator

Reputation: 45674

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.

Upvotes: 3

Ofir
Ofir

Reputation: 8362

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

Upvotes: 2

Related Questions