How does knowing the input size make the time complexity of a function constant?

Question

After reading the question and answers on Time complexity of min() and max()? I would like to clear up some confusion on the relation between time complexity and size of input.

First, I've noticed most of the time people omit what exactly n represents in big O notation. Usually it's related to the input, but it may be the value or length in bits or something else. Am I right that it's usually inferred from context?

When is a function O(1) vs O(n)? I had thought that only functions that do not depend on the input would be O(1) for example

foo()
{
  return "bar"
}

Or accessing certain data structures like an array arr[0] or a map would have operations of O(1). But in the linked question some answers stated this is only true if the size is known. What difference does this make? Even if the size is known, some operations may take O(n). For example given in an array of 100 elements you know the value 50 appears and would like to find its index. That would be O(n) because the array would have to be traversed. So why do some people say knowing the size makes it constant time?

Answer 1

First, I've noticed most of the time people omit what exactly n represents in big O notation.

Yes, that is indeed a bad habit. In general, when you analyze complexity, you must specify:

• Are you talking about space complexity, step complexity, time complexity?
• Are you talking about best-case, worst-case, amortized worst-case, average case, expected case?
• What is your machine model? (I.e. what operations exist?)
• What is your cost model? (How long do those operations take?)
• What are you actually counting? (Comparisons, stores, loads, arithmetic operations, bit operations, etc.)
• How do you define "length of the input"? (Number of elements, number of bits, etc.)
• What is the distribution of your inputs? (In case of average or expected complexity.)

Usually it's related to the input, but it may be the value or length in bits or something else.

For data structures, it is usually the number of elements. For strings, it already gets trickier: is it the number of bytes, number of octets, number of `chars, number of code points, number of characters, number of graphemes, number of grapheme clusters?

One thing that catches many people out is that for numbers, it is usually not the magnitude, it is the length (i.e. the number of "digits" or bits), which is the logarithm of the magnitude.

Am I right that it's usually inferred from context?

Indeed. However, as mentioned above, for numbers, it is often inferred wrong.

The reason why we usually use the length of numbers is that arithmetic operations depend on the number of digits, not on the magnitude of the number: adding 1+1 take the same time as adding 4+4, but adding 10+10 takes twice as long. Adding 4999+5000 doesn't take 5000 times as long as adding 1+1, it only takes 4 times as long.

For example given in an array of 100 elements you know the value 50 appears and would like to find its index. That would be O(n) because the array would have to be traversed.

No, it would not. O(1) means the number of comparisons (which is what we are usually counting when talking about "searching") is bounded by a constant. In your example, you will never need more than 100 comparisons, therefore the number of comparisons is bounded by 100, which is a constant.

Therefore, the time complexity is O(100), which is the same as O(1).

Answer 2

This can be summed up in one sentence that you should memorise:

In complexity theory, what we call a "problem" is never one question, but instead an infinite family of questions that depend on an input.

For each input, there is a question.

An algorithm is said to solve the problem if for any input, the algorithm is able to find the answer to the question. Upper bounds and lower bounds on the complexity of an algorithm that solves a problem are expressed as a function of the size of the input.

With these definitions in mind, a problem that doesn't depend on an input can be solved in O(1) by definition, and a problem whose input is artificially limited in size can be solved in O(1) by definition. Only problems whose input can grow arbitrarily large are "interesting" from the point of view of complexity theory.

Constant Connect-Four vs. unbounded Connect-Four

For instance, the problem "Given a position of 7x6 Connect-Four, does the first player have a winning strategy?" is a boring O(1) problem from the theoretical point of view of complexity theory. You can imagine many algorithms to solve this problem, and all of them will have O(1) complexity by definition, which tells us nothing. For instance, one possible algorithm is to hardcode all $3^{42}$ possible positions and their answers in a lookup table. Technically this algorithm only uses O(1) space, even though $3^{42}$ is a huge number (about two hundred million million millions). Another possible naive algorithm is to explore the whole tree of possible plays from the given position, running a minmax algorithm to determine each player's best moves; this would have time complexity $7^{42}$, which again is a gargantuan number, but technically O(1).

This is of course a disappointing answer, and certainly we want to say that some algorithms are more efficient than others. Our intuition tells us that 6x7 shouldn't be treated as a constant. But complexity theory only studies the growth of complexity as input size grows, so if you don't allow input size to grow, then by definition the theory cannot do anything.

So instead of studying "classic 7x6 Connect-Four", you can study the more general problem "cxr Connect-Four", a generalisation of classic Connect-Four played on a board with c columns and r rows. Now you can't hardcode all the answers in a lookup table, because the problem is an infinite family of questions, for arbitrarily-large board sizes. And now you can express upper bounds and lower bounds on the complexity of an algorithm as a function of c and r, or as a function of n=cr to simplify. Now it can be said that a time complexity of $c^{cr}$ is terrible, and the theory is able to distinguish between an efficient algorithm and a terribly-slow algorithm.

Searching for a substring of size k in a string of size n

Sometimes instead of just one number n, there can be several numbers that depend on the input and that are relevant to algorithms' complexity. For instance, the problem "Find the index of a substring in a string" can be solved by a naive algorithm in time $O(nk)$, where $n$ is the length of the big string ("the haystack") and $k$ is the length of the substring ("the needle").

If the input is just the haystack and the needle, and there is no constraint on $k$ and $n$, then the size of the input is $N = k + n$ and if we want to express the complexity of the naive algorithm with respect to $N$, all we can say is that this algorithm has quadratic complexity, ie in the worst case it grows proportionally to $N^2$. This worst-case is realised for instance whenever $k = \frac{1}{2}n = \frac{1}{3}N$, because in those cases $nk = \frac{2}{9}N^2 = Θ(N^2)$.

However, a variant of this problem is the similar problem, but with $k$ bounded by a constant. In this case, the naive algorithm has linear complexity, because $kn = k(N-k) = Θ(N)$.

Studying this "k is bounded" variant makes sense; it's a subproblem where we limit ourselves to searching small needles in arbitrarily large haystacks, so we don't want to be pessimistic and calculate worst-case complexities that allow $k$ to grow proportionally with $N$. We want to favour algorithms whose complexity grows lowly with $n$, even if the tradeoff is that the complexity grows highly with $k$; and we do that by declaring that $k$ is guaranteed not to grow.