This content has been automatically translated from Ukrainian.
Factorial complexity is a situation where the number of options or combinations grows like the factorial of the number of elements. In other words, for n elements, the possible permutations are n!n!n! (n factorial), which quickly becomes a huge number even for small n.
This phenomenon is often encountered in combinatorics, planning, and exhaustive algorithms. For example, the permutations of 5 elements are 120 options, while for 10 elements, there are already 3,628,800.
Real-life examples:
- Permutations of tasks or routes – planning delivery routes or tasks in a project.
- Playing chess or puzzles – the number of possible sequences of moves grows extremely quickly.
- Cryptography – guessing combinations or passwords through exhaustive search.
A simple Ruby code to demonstrate factorial complexity:
def factorial(n)
(1..n).reduce(1, :*)
end
(1..10).each do |i|
puts "n=#{i} - #{factorial(i)} options"
end
Result:
n=1 - 1 options n=2 - 2 options n=3 - 6 options n=4 - 24 options n=5 - 120 options n=6 - 720 options n=7 - 5040 options n=8 - 40320 options n=9 - 362880 options n=10 - 3628800 options => 1..10
This example shows why factorial complexity quickly complicates the task and makes direct enumeration of options practically impossible.
This post doesn't have any additions from the author yet.
