What is an algorithm?
An algorithm is a clear, step-by-step procedure for solving a problem. A recipe is an algorithm for cooking.
A good algorithm is correct, efficient and clear.
Example: finding the largest number
def find_max(numbers):
largest = numbers[0]
for n in numbers:
if n > largest:
largest = n
return largest
print(find_max([4, 9, 2, 7])) # 9Measuring efficiency: Big-O
Big-O notation describes how the work grows as the input size n grows. It ignores small details and focuses on the trend.
| Notation | Name | Example |
|---|---|---|
| O(1) | Constant | Reading an array element by index |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Looping through a list once |
| O(n log n) | Linearithmic | Efficient sorting (merge sort) |
| O(n²) | Quadratic | Two nested loops |
| O(2ⁿ) | Exponential | Trying every subset |
Linear vs binary search
def linear_search(items, target):
for i, value in enumerate(items): # O(n)
if value == target:
return i
return -1
def binary_search(sorted_items, target): # O(log n), list must be sorted
low, high = 0, len(sorted_items) - 1
while low <= high:
mid = (low + high) // 2
if sorted_items[mid] == target:
return mid
if sorted_items[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1For a list of one million items, linear search may need up to a million checks, while binary search needs about twenty.
Sorting
Simple sorts such as bubble sort are O(n²). Merge sort and quicksort are typically O(n log n). In real projects, use your language's built-in sort.
Space complexity
Big-O also describes memory use. Sometimes you trade memory for speed, such as storing results in a dictionary so you do not compute them twice.
Practice
Write a function to find duplicates in a list in O(n) time using a set, and explain why your first nested-loop version is O(n²).