Speed of algorithms (with cats)
Tags: algorithms, beginners
Published: 2022-12-22 08:52:06

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.

![Constant time](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9dh29ba50l2txlwxhzhc.jpg)

## 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.

![Logarithmic time](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wrvm6iwx791zvi5h7pfh.jpg)

## 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.

![Linear time](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/yrxdaz6bfw69r2ao55lr.jpg)

## 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.

![Log-linear time](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pyv8mnt5p5lrwj0aobnx.jpg)

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.

![Quadratic time](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/urzjqy23yqgn36d717jz.jpg)

## 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 time](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5by92yks3jr8lty10n7e.jpg)

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.

![Exponential time](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7l6cchsipqafkqirlxpg.jpg)

## 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.

![Factorial time](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tyke2tw3kq7oa9icargv.jpg)

## 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](https://twitter.com/ohmypy)** on Twitter to keep up with new posts 🚀_