And now for something completely different.
It's been a while since we've had fun with mathematics so I'm going to put you to work. I want an elegant way to explain algorithmic complexity to people who never heard of it before, and I want to back up that explanation with concrete examples that are closely related to one another. Let me explain.
As the nerdier of you will know, different problems have different algorithmic complexities, as in:
- O(1): constant time
- O(log n): logarithmic
- O(n): linear
- O(n log n): ... whatever the hell that's called ...
- O(n^2): n squared, or quadratic
- O(n^3): n cubed (cubic)
- O(2^n): exponential (ouch)
- O(n!): n factorial (serious ouch)
and so on.
What I want to do is demonstrate each type of complexity with an actual problem but, to make it even clearer, I want those problems to be closely related -- as in, starting with a common set of data.
For example, if I start with a random handful of playing cards, it's easy to define a few problems with different complexities using those same cards:
- pick a random card: O(1)
- find the largest card: O(n)
- sort the cards: O(n log n)
But once I list those examples, what's left? Can I use those same cards to show a problem that has quadratic complexity? Or cubic complexity? And so on. I don't think so -- at least I can't think of any. So I don't think there's much that can be done with that handful of random playing cards.
So what else is there? What I'm after is some initial set of data that's trivially easy to describe, but allows for the definition of various problems with as many different complexities as possible. I already have a couple ideas but I'm not giving any hints. You're on your own.
JUST SO YOU UNDERSTAND, I really do know my computational complexity and NP stuff, and I'm quite capable of producing problems whose solutions have one of the complexities above. What I'm after -- as I'm sure most of you now realize -- is a relatively simple starting scenario whose variations will produce as many different complexities as possible.
So while the weighted knapsack problem is a good example of a particular complexity, can you generalize it to invent other problems of other complexities? It is a promising direction as it's something I thought of fairly quickly.