Algorithms: Learning One's Learnings

When I studied algorithms more than twenty years ago, I saw their general usefulness, but since then, I have never had to use them in the real world because they had already been implemented by database management services or built-in functionalities of most programming languages that I used. Interviewer: Can you sort this list by size? Interviewee: Absolutely. /types confidently.../ l.sort() There came a time when I had to remind myself of sorting algorithms. At 1st things 1st, I was about to implement a feature that lets users prioritize their options by comparing them two at a time. I thought that the Bubble Sort algorithm would fit perfectly. So, I built the UI using ReactJS and Django for the backend to let users compare options and sort their priorities. However, I soon noticed a problem: for longer lists, the process became quite time-consuming for users. One day, I remembered something about algorithm complexity (also known as Big O Notation) and realized that Bubble Sort isn't the most efficient choice for this task. In computer science, Big O notation describes how the performance of an algorithm grows relative to the size of the input. It's usually written like O(value), where value is a function of n, and n is the number of items the algorithm processes. For example: Finding the first item in a list or a key in a dictionary of n items is O(1). Summing all items by iterating through a list is O(n). Using a triple nested loop over the list would result in O(n³). Here is an overview of most common complexities: Complexity Name Meaning and Example O(1) Constant Always the same time, no matter input size, e.g. accessing an array item O(log n) Logarithmic Doubles size, just +1 step, e.g. Binary Search O(n) Linear Time grows with size, e.g. loop over list O(n log n) Linearithmic "Almost linear", but a bit slower, e.g. Merge Sort O(n²) Quadratic Time explodes with size, e.g. nested loops as in Bubble sort O(2ⁿ) Exponential Be careful — grows crazy fast, e.g. Recursive Fibonacci O(n!) Factorial Nightmare mode, e.g. solving Traveling Salesman by brute force Understanding the Big O practically Bubble Sort is an algorithm with a time complexity of O(n²). That means: if you have a list of items, the algorithm needs to compare each item against many others, using two nested loops. To sort a list of 5 items, the user might need up to 25 comparisons. To sort 10 items, up to 100 comparisons. To sort 50 items, up to 2,500 comparisons. Not ideal. I asked ChatGPT to help evaluate sorting algorithms based on their complexity, and Quick Sort came out as a much better choice. Its complexity is O(n log n), where log n (base 2) roughly means "how many times you can divide n by 2 until you reach 1." To sort 5 items, Quick Sort would need around 12 comparisons. To sort 10 items, around 34 comparisons. To sort 50 items, around 282 comparisons. That's still some work, but much more manageable. From a usability perspective, though, it’s even better to let users drag and drop items manually or to offer AI-suggested orderings. So I implemented those options too. Algorithm complexities in action Below is a quick cheat sheet with complexities from the fastest to the slowest: Sorting algorithms Algorithm Best Case Average Case Worst Case Notes Timsort O(n) O(n log n) O(n log n) Used in Python, Java Merge Sort O(n log n) O(n log n) O(n log n) Stable, reliable Heap Sort O(n log n) O(n log n) O(n log n) In-place Quick Sort O(n log n) O(n log n) O(n²) Fastest on average Shell Sort O(n log n) O(n¹·⁵) O(n²) Improved insertion Insertion Sort O(n) O(n²) O(n²) Good for small/mostly sorted data Selection Sort O(n²) O(n²) O(n²) Simple but slow Bubble Sort O(n) O(n²) O(n²) Only good for tiny lists Search algorithms Algorithm Best Case Average Case Worst Case Notes Hash Table Search O(1) O(1) O(n) Worst case rare (collisions) Binary Search O(1) O(log n) O(log n) Needs sorted data Jump Search O(1) O(√n) O(√n) For sorted arrays Ternary Search O(1) O(log n) O(log n) Split into three parts Linear Search O(1) O(n) O(n) No sorting needed, but slow Encryption algorithms Algorithm Complexity Notes AES (Advanced Encryption Standard) O(1) per block Very fast, symmetric key ChaCha20 O(1) per block Modern stream cipher, very fast RSA Encryption O(n³) Public key, slow for big data Elliptic Curve Cryptography (ECC) O(n²) Faster than RSA at similar security Diffie-Hellman Key Exchange O(n³) Secure key exchange, slower Just for the hunger of interest Python, MySQL, and PostgreSQL use these algorithms behind the scenes: System Sorting Algorithm Notes Python sort() and sorted() Timsort Hybrid of Merge Sort + Insertion Sort MySQL ORDER BY Quicksort (small datasets), Merge Sort or Filesort (large datasets) Depends on storage engine (InnoDB, etc.) PostgreSQL ORDER BY

May 1, 2025 - 23:45

When I studied algorithms more than twenty years ago, I saw their general usefulness, but since then, I have never had to use them in the real world because they had already been implemented by database management services or built-in functionalities of most programming languages that I used.

Interviewer: Can you sort this list by size?

Interviewee: Absolutely.
/types confidently.../
l.sort()

There came a time when I had to remind myself of sorting algorithms. At 1st things 1st, I was about to implement a feature that lets users prioritize their options by comparing them two at a time. I thought that the Bubble Sort algorithm would fit perfectly.

So, I built the UI using ReactJS and Django for the backend to let users compare options and sort their priorities.

However, I soon noticed a problem: for longer lists, the process became quite time-consuming for users.

One day, I remembered something about algorithm complexity (also known as Big O Notation) and realized that Bubble Sort isn't the most efficient choice for this task.

In computer science, Big O notation describes how the performance of an algorithm grows relative to the size of the input. It's usually written like O(value), where value is a function of n, and n is the number of items the algorithm processes.

For example:

Finding the first item in a list or a key in a dictionary of n items is O(1).
Summing all items by iterating through a list is O(n).
Using a triple nested loop over the list would result in O(n³).

Here is an overview of most common complexities:

Complexity	Name	Meaning and Example
`O(1)`	Constant	Always the same time, no matter input size, e.g. accessing an array item
`O(log n)`	Logarithmic	Doubles size, just +1 step, e.g. Binary Search
`O(n)`	Linear	Time grows with size, e.g. loop over list
`O(n log n)`	Linearithmic	"Almost linear", but a bit slower, e.g. Merge Sort
`O(n²)`	Quadratic	Time explodes with size, e.g. nested loops as in Bubble sort
`O(2ⁿ)`	Exponential	Be careful — grows crazy fast, e.g. Recursive Fibonacci
`O(n!)`	Factorial	Nightmare mode, e.g. solving Traveling Salesman by brute force

Understanding the Big O practically

Bubble Sort is an algorithm with a time complexity of O(n²). That means: if you have a list of items, the algorithm needs to compare each item against many others, using two nested loops.

To sort a list of 5 items, the user might need up to 25 comparisons.
To sort 10 items, up to 100 comparisons.
To sort 50 items, up to 2,500 comparisons.

Not ideal.

I asked ChatGPT to help evaluate sorting algorithms based on their complexity, and Quick Sort came out as a much better choice. Its complexity is O(n log n), where log n (base 2) roughly means "how many times you can divide n by 2 until you reach 1."

To sort 5 items, Quick Sort would need around 12 comparisons.
To sort 10 items, around 34 comparisons.
To sort 50 items, around 282 comparisons.

That's still some work, but much more manageable.

From a usability perspective, though, it’s even better to let users drag and drop items manually or to offer AI-suggested orderings. So I implemented those options too.

Algorithm complexities in action

Below is a quick cheat sheet with complexities from the fastest to the slowest:

Sorting algorithms

Algorithm	Best Case	Average Case	Worst Case	Notes
Timsort	`O(n)`	`O(n log n)`	`O(n log n)`	Used in Python, Java
Merge Sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	Stable, reliable
Heap Sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	In-place
Quick Sort	`O(n log n)`	`O(n log n)`	`O(n²)`	Fastest on average
Shell Sort	`O(n log n)`	`O(n¹·⁵)`	`O(n²)`	Improved insertion
Insertion Sort	`O(n)`	`O(n²)`	`O(n²)`	Good for small/mostly sorted data
Selection Sort	`O(n²)`	`O(n²)`	`O(n²)`	Simple but slow
Bubble Sort	`O(n)`	`O(n²)`	`O(n²)`	Only good for tiny lists

Search algorithms

Algorithm	Best Case	Average Case	Worst Case	Notes
Hash Table Search	`O(1)`	`O(1)`	`O(n)`	Worst case rare (collisions)
Binary Search	`O(1)`	`O(log n)`	`O(log n)`	Needs sorted data
Jump Search	`O(1)`	`O(√n)`	`O(√n)`	For sorted arrays
Ternary Search	`O(1)`	`O(log n)`	`O(log n)`	Split into three parts
Linear Search	`O(1)`	`O(n)`	`O(n)`	No sorting needed, but slow

Encryption algorithms

Algorithm	Complexity	Notes
AES (Advanced Encryption Standard)	`O(1)` per block	Very fast, symmetric key
ChaCha20	`O(1)` per block	Modern stream cipher, very fast
RSA Encryption	`O(n³)`	Public key, slow for big data
Elliptic Curve Cryptography (ECC)	`O(n²)`	Faster than RSA at similar security
Diffie-Hellman Key Exchange	`O(n³)`	Secure key exchange, slower

Just for the hunger of interest

Python, MySQL, and PostgreSQL use these algorithms behind the scenes:

System	Sorting Algorithm	Notes
Python `sort()` and `sorted()`	Timsort	Hybrid of Merge Sort + Insertion Sort
MySQL `ORDER BY`	Quicksort (small datasets), Merge Sort or Filesort (large datasets)	Depends on storage engine (InnoDB, etc.)
PostgreSQL `ORDER BY`	Quicksort (small data), Heapsort + Mergesort for bigger sets	Intelligent memory-aware switching

Final words

So if you ever have to solve a development issue algorithmically instead of using default libraries — or even when choosing an algorithm from a library — remember the Big O notation. Sometimes the difference can save milliseconds or seconds of time, and sometimes, when users' input is involved, it can save minutes or even hours.

Cover picture by Steve Johnson