Real-world example of exponential time complexity
I'm looking for an intuitive, real-world example of a problem that takes (worst case) exponential time complexity to solve for a talk I am giving.
Here are examples for other time complexities I have come up with (many of them taken from this SO question):
- O(1) - determining if a number is odd or even
- O(log N) - finding a word in the dictionary (using binary search)
- O(N) - reading a book
- O(N log N) - sorting a deck of playing cards (using merge sort)
- O(N^2) - checking if you have everything on your shopping list in your trolley
- O(infinity) - tossing a coin until it lands on heads
Any ideas?
Answer
- O(10^N): trying to break a password by testing every possible combination (assuming numerical password of length N)
p.s. why is your last example is of complexity O(infinity) ? it's linear search O(N) .. there are less than 7 billion people in the world.