What is an algorithm?
An algorithm is a set of instructions that accomplish a task. It could be a cake recipe, an assembly manual, or in our case, a procedure that a computer follows to solve a problem.
The difference between a good algorithm and a bad one can be the difference between solving something in 30 operations or in 1 billion. That is exactly what we will cover here.
Binary Search
Imagine you are looking for a name in a phone book with 128 names sorted alphabetically. The most naive approach would be to check each name from start to finish. In the worst case, you would make 128 checks.
Binary search works much smarter: you open the book in the middle, check whether the name you are looking for comes before or after, and discard half of the items at once. Then you repeat the process on the remaining half.
With 128 names, the maximum number of steps is 7 (because log2 128 = 7). If the list has 256 names, it takes only 8 steps. We doubled the input and added just one extra step.
Fundamental requirement
Binary search only works with sorted lists. If the list is not in order, you need to sort it first or use a different search method.
Python implementation
def binary_search(lst, target):
low = 0
high = len(lst) - 1
while low <= high:
mid = (low + high) // 2
guess = lst[mid]
if guess == target:
return mid
if guess > target:
high = mid - 1
else:
low = mid + 1
return None # not found
# Usage example
my_list = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(my_list, 7)) # 3 (index of the element)
print(binary_search(my_list, 10)) # NoneAt each iteration, the search space is halved. This results in a complexity of O(log n).
Logarithms
If exponentiation is multiplying a base by itself multiple times, the logarithm is the inverse operation: it answers “how many times do I need to multiply the base to reach this number?”.
- log10 100 = 2 — I need to multiply 10 by itself 2 times to reach 100 (10 x 10 = 100)
- log2 128 = 7 — I need to multiply 2 by itself 7 times to reach 128
- log2 256 = 8 — one more than 128, because we doubled the number
In computer science, when we say O(log n), we usually mean log base 2. That is why binary search is so efficient: each step eliminates half the problem.
Big O Notation
Big O notation describes how an algorithm scales as the input size grows. It does not measure time in seconds, but rather the number of operations in the worst case.
Practical comparison
Consider a list with 1 billion elements (10^9):
| Algorithm | Operations |
|---|---|
| Simple search O(n) | 1,000,000,000 |
| Binary search O(log n) | ~30 |
The difference is staggering. While simple search needs to check every element, binary search solves the problem in about 30 steps.
Most common complexities
| Notation | Name | Example |
|---|---|---|
| O(1) | Constant | Accessing an array element by index |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Simple search (traverse the entire list) |
| O(n log n) | Linearithmic | Quicksort, Merge sort |
| O(n^2) | Quadratic | Selection sort, nested loops |
| O(n!) | Factorial | Travelling salesman (brute force) |
What does it mean in practice?
To get a concrete idea, see how many operations each complexity requires for different input sizes:
| n | O(1) | O(log n) | O(n) | O(n log n) | O(n^2) | O(n!) |
|---|---|---|---|---|---|---|
| 10 | 1 | ~3 | 10 | ~33 | 100 | 3,628,800 |
| 100 | 1 | ~7 | 100 | ~664 | 10,000 | impossible |
| 1,000 | 1 | ~10 | 1,000 | ~9,966 | 1,000,000 | impossible |
The O(n!) complexity is particularly terrifying: for n = 20, we are talking about roughly 2.4 quintillion operations. That is why problems like the travelling salesman have no efficient exact solution for large inputs.
Arrays vs Linked Lists
Before discussing Quicksort, it is worth understanding two fundamental data structures.
Arrays
- Store elements in sequential positions in memory
- Reading by index is instant: O(1)
- Insertion is problematic: if there is no contiguous space available, all elements need to be moved — O(n)
- Size is generally fixed (or requires reallocation)
Linked lists
- Each element holds a reference (pointer) to the next one
- Items can be scattered across memory
- Insertion is fast: just update the pointers — O(1)
- Reading by position requires traversing the list from the beginning — O(n)
Comparative summary
| Operation | Array | Linked list |
|---|---|---|
| Reading | O(1) | O(n) |
| Insertion | O(n) | O(1) |
| Deletion | O(n) | O(1) |
When to use each?
- Arrays: when you need to access elements by index frequently (e.g., price table, ranking)
- Linked lists: when insertions and removals are frequent and sequential reading is acceptable (e.g., task queue, playlist)
In practice, most modern languages offer hybrid structures (like ArrayList in Java or list in Python) that combine the best of both worlds.
Quicksort
Quicksort is one of the most widely used sorting algorithms in practice. It uses the Divide and Conquer technique, which consists of:
- Defining a base case (usually an empty array or one with a single element, which is already sorted)
- Reducing the problem until you reach the base case
Divide and Conquer
The DC (Divide and Conquer) technique is a general strategy for solving problems:
- Divide the problem into smaller subproblems
- Conquer each subproblem recursively
- Combine the results
Binary search also uses this logic: it halves the search space at each step. Quicksort applies the same principle to sorting.
How it works
- Choose an element as the pivot
- Partition the array into two sub-arrays: elements smaller than the pivot and elements larger than the pivot
- Apply Quicksort recursively on each sub-array
- Combine the results
Python implementation
def quicksort(lst):
if len(lst) < 2:
return lst # base case: empty list or single element
pivot = lst[0]
smaller = [i for i in lst[1:] if i <= pivot]
greater = [i for i in lst[1:] if i > pivot]
return quicksort(smaller) + [pivot] + quicksort(greater)
# Usage example
print(quicksort([10, 5, 2, 3])) # [2, 3, 5, 10]
print(quicksort([33, 15, 10, 7])) # [7, 10, 15, 33]Pivot selection
Pivot selection directly impacts performance:
- Fixed pivot (first element): simple but dangerous. If the array is already sorted, Quicksort degrades to O(n^2)
- Random pivot: recommended strategy. By choosing randomly, the probability of hitting the worst case is very low
- Median of three: picks the median of the first, middle, and last element. A good heuristic
Complexity
| Case | Complexity | When it happens |
|---|---|---|
| Best case | O(n log n) | Pivot splits the array in half |
| Average case | O(n log n) | Random pivot, reasonable splits |
| Worst case | O(n^2) | Pivot is always the smallest or largest element |
In practice, the average case is the most common, and Quicksort tends to be faster than other O(n log n) algorithms like Merge Sort due to smaller constants and better cache usage.
Conclusion
These concepts form the foundation for understanding the efficiency of any software:
- Binary search turns searches of billions of operations into dozens
- Big O gives us a common language to compare algorithms
- Arrays and linked lists have clear trade-offs that impact performance
- Quicksort shows how the Divide and Conquer technique solves sorting problems elegantly
Understanding algorithms is not just an academic exercise. It is what separates a system that handles scale from one that crashes with a thousand users.