Return to Answer

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 ≈ kN = Θ(N)$.

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

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 42!, the factorial of 42, which again is a gargantuan number, but technically O(1).

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 n! is terrible, and the theory is able to distinguish between an efficient algorithm and a terribly-slow algorithm.

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

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

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.

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.

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

This is of course a disappointing answer, and certainly we want to say that some algorithms are more efficient than others. 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.

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 as large as $N/2$.

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 42!, the factorial of 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 n! is terrible, and the theory is able to distinguish between an efficient algorithm and a terribly-slow algorithm.

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