Speed of algorithms (with cats)

Let's see how programmers evaluate fast and slow algorithms. Since the topic is pretty boring, we'll use silly cat examples.

Constant time: O(1)

This is your best option. The algorithm speed does not depend on the number of cats.

🐾 Example
You are the lucky owner of N cats. Every kitten knows their name. If you call "Felix!", only one will come running, and the rest of the N-1 fluffs don't care.

Logarithmic time: O(log n)

On N cats the algorithm completes in log(N) steps. It's fast! 1,000,000 kittens → 20 operations total.

🐾 Example
Cat's bowls are arranged alphabetically. When you adopt a new cat, the place for its bowl can be found in log(N) steps.

Linear time: O(n)

On N cats the algorithm completes in N steps. It means that every time you have to traverse all cats. Not great, not terrible.

🐾 Example
Your kittens rebelled and stopped responding to nicknames. Now you have to look through N fluffs to find the right one.

Log-linear time: O(n log n)

On N cats the algorithm completes in N × log(N) steps. This is slower than in linear time, but not by much (the logarithm of N is much smaller than N, remember?).

🐾 Example
Waiting for guests, you decided to seat kittens in the order of their size. The quick sort algorithm will handle this in N × log(N) steps.

Next in line, we have lazy polynomial cats and snail-speed superpolynomial ones.

Quadratic time: O(n²)

On N cats the algorithm completes in N² steps. So slow.

🐾 Example
Your competitor claims that his N kittens are smoother and happier than yours. A special commission will compare the cats in pairs and make a fair verdict. You will need ~ N² comparisons.

Polynomial time: O(nᵏ)

On N cats the algorithm completes in N³ steps, N⁴ steps, N⁵ steps, or even longer. Ugh. Don't be like that.

🐾 Example
Photoshoot! Each of the N kittens will be photographed in pairs with others, and the photographer takes N pictures for each pair. N × N × N ≃ N³ steps.

Polynomial algorithms are not famous for their speed. But compared to superpolynomial ones, they are as fast as a Flash. Sadly, the only "super" part of superpolynomial algorithms is a name. Let me show you.

Exponential time: O(2ⁿ)

On N cats the algorithm completes in 2ⁿ steps. It's a long time, you're probably not gonna wait.

🐾 Example
Kittens are going to the cat show. Everyone will be weighed and rated in stars. But the cat transport can handle a maximum of X kilograms (or pounds). How to choose the most stellar cast? The answer will require 2ⁿ steps.

Factorial time: O(n!)

On N cats the algorithm completes in N ×(N-1) ×(N-2) ×... × 1 steps. This is crazy! With 20 cats it's already a couple of quintillion operations.

🐾 Example
Kittens spread out across the apartment. You want to pet everyone, but you're lazy and don't like walking. What is the shortest route to visit all fluffs? This is ~ N! comparisons.

Summary

Here are the algorithms we've covered:

• Constant O(1)
• Logarithmic O(log n)
• Linear O(n)
• Log-Linear O(n log n)
• Quadratic O(n²)
• Polynomial O(nᵏ)
• Exponential O(2ⁿ)
• Factorial O(n!)

A constant algorithm is always the best option, and a logarithmic one is almost always. Linear and polynomial ones are more complex — it all depends on the task with them. Sometimes it's a shame to choose O(n), and sometimes O(n²) is a huge success.

O(2ⁿ) and O(n!) are insanely slow. So in practice, people often use suboptimal but fast algorithms.

Follow @ohmypy on Twitter to keep up with new posts 🚀