#combinatorial explosion

This problem illustrates how common, every day Web functionality presents the test designer with a staggeringly large number of execution paths.

Imagine you have a shopping cart which can contain up to 100 different items in varying quantities. There are about 150 different items to choose from.

Now imagine you have been asked to design an automated test that exercises all possible combinations of items, in all valid quantities including zero.

How many variables do we need to think about here? There are 3 variables:

capacity of the cart,

number of different items, and

how many of each item is available

How would you describe the complexity of this test? The number of paths that need be excercised exhibits factorial or O(n!) growth as we put more items into the cart.

How long would you expect this test to take to run? There are over 10^45 ways (that's the sum of 150 choose i as i grows from 1 to 100) to fill the cart with just one of each item. That's just one of each item, we haven't even considered different quantities of items yet.

Assuming one test per microsecond, runtime exceeds the age of the universe (only about 4 * 10^17 seconds). And that still is just a fraction of the number of paths that would be encountered in the the full test case as described above; where not just all possible combinations of items, but also all possible combinations in all valid quantities from 0 to 100, would be tested. I didn't bother to do the math on that one, but it's a lot of paths :)

"The Astronomical Math Behind UPS’ New Tool to Deliver Packages Faster" via Wired