41

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?

Community
  • 1
  • 1
del
  • 6,341
  • 10
  • 42
  • 45
  • 3
    Homework ಠ_ಠ or just casual interest? – hayesgm Aug 14 '11 at 07:53
  • 4
    does it matter? – csguy Jan 06 '20 at 04:08
  • 1
    Intuitively the shopping cart example seems wrong. It feels more like linear. I go once through the list and reading an item I remember if I put it in the cart. It seems like the lookup is O(1) like in a hashmap or associative memory. – Chris Jun 19 '20 at 22:08

5 Answers5

38
  • 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.

Aziz
  • 20,065
  • 8
  • 63
  • 69
  • Because new people are born every second, so in the worst case you could search the world forever without ever finding anyone born on 1 January. I understand your point though, it's probably not the best example. – del Aug 14 '11 at 08:05
  • ...and I have just changed the example in the question. – del Aug 14 '11 at 08:11
  • I see ... well, it makes sense because your problem size (number of people in the world) is infinitely increasing. – Aziz Aug 14 '11 at 08:13
  • 1
    @Aziz, Is `O(infinity)` merely a joke, or is it actually a *valid* notation? – Pacerier Jun 25 '14 at 22:10
  • 1
    @Pacerier: As far as I know, an algorithm is `O(infinity)` if it can potentially never terminate, like the OP's example, "tossing a coin until it lands on heads". – Aziz Jul 20 '14 at 04:10
  • @Aziz, I meant regardless of how long it takes to run, is that notation even *valid*? – Pacerier Jul 21 '14 at 22:34
  • @Pacerier: I don't really know. What exactly do you mean by "valid"? – Aziz Jul 25 '14 at 14:53
  • @Pacerier: I don't know the answer to that. I think it's a good question to ask in http://cstheory.stackexchange.com/ – Aziz Jul 28 '14 at 14:11
8

A pizza restaurant has several toppings to choose from

  • Pepperoni
  • Chilli peppers
  • Pineapple (don't knock it until you've tried it!)

Customers may choose any combination of toppings or none at all for their pizza. Now consider an algorithm that finds every possible unique combination of toppings. This is an exponential algorithm with time complexity O(2^n).

Look how the possible combinations grow (exponentially) when you add a new topping to the menu:

0 toppings: 1 combination (no toppings at all)
1 toppings: 2 combinations (none, a)
2 toppings: 4 combinations (none, a, b, ab)
3 toppings: 8 combinations (none, a, b, c, ab, ac, bc, abc)
...
...
10 toppings: 1,024 combinations
20 toppings: 1,048,576 combinations

So with just 20 types of toppings, there are over 1 million possible combinations!

MrCode
  • 63,975
  • 10
  • 90
  • 112
1

A brute-force and naive n-queens problem's solution.

You have to place n queens on a n*n board without them to be taken by others.

while there are untried configs, go to next solution and test it

Assuming every queen is on a given row, there are n possibilities for the queen to be placed and n for the (n-1) other queens (because duplicate rows are not checked).

Therefore, you've got a O(n^n) complexity

Cydonia7
  • 3,744
  • 2
  • 23
  • 32
0

What about finding a subset of integers within a set such that their sum is a designated value X?

I believe this has complexity O(2^(n/2))

dmcshane784
  • 9
  • 2
0

The brute force solution of the traveling salesman problem is O(n!) which is approximately O(N^N)

Brett Walker
  • 3,566
  • 1
  • 18
  • 36
  • 9
    A brute force on the TSP is factorial time, not exponential. Those are two different orders of complexity. – Vivien Barousse Aug 14 '11 at 08:01
  • 1
    I'm looking for a more intuitive everyday-type problem that a wider audience will understand. A lot of people are unfamiliar with the TSP (software developers included). – del Aug 14 '11 at 08:02
  • @Brett, What is O(N^N) called? Is it "exponential square"? – Pacerier Jun 25 '14 at 22:11