Combinatorial Explosion
The main disadvantage of the brute-force method is that, for many real-world problems, the number of natural candidates is prohibitively large. For instance, if we look for the divisors of a number as described above, the number of candidates tested will be the given number n. So if n has sixteen decimal digits, say, the search will require executing at least 1015 computer instructions, which will take several days on a typical PC. If n is a random 64-bit natural number, which has about 19 decimal digits on the average, the search will take about 10 years. This steep growth in the number of candidates, as the size of the data increases, occurs in all sorts of problems. For instance, if we are seeking a particular rearrangement of 10 letters, then we have 10! = 3,628,800 candidates to consider, which a typical PC can generate and test in less than one second. However, adding one more letter — which is only a 10% increase in the data size — will multiply the number of candidates by 11 — a 1000% increase. For 20 letters, the number of candidates is 20!, which is about 2.4×1018 or 2.4 quintillion; and the search will take about 10 years. This unwelcome phenomenon is commonly called the combinatorial explosion.
Read more about this topic: Brute-force Search
Famous quotes containing the word explosion:
“Frau Stöhr ... began to talk about how fascinating it was to cough.... Sneezing was much the same thing. You kept on wanting to sneeze until you simply couldn’t stand it any longer; you looked as if you were tipsy; you drew a couple of breaths, then out it came, and you forgot everything else in the bliss of the sensation. Sometimes the explosion repeated itself two or three times. That was the sort of pleasure life gave you free of charge.”
—Thomas Mann (1875–1955)