Algorithms and their speed (Big-O)
What an algorithm is, counting steps, O(1), O(n), O(n²), O(log n)
An algorithm is a precise sequence of steps for solving a problem. A recipe is an algorithm too: follow it in order and the result is the same.
One problem can have several solutions. Which is better? Usually what matters is which one stays fast as the data grows. With 10 items every algorithm is fast; with 10 million the difference can be hours.
Let's count steps
Does a list contain a duplicate? Two solutions:
def has_dup_1(r): # compare every pair
steps = 0
for i in range(len(r)):
for j in range(i + 1, len(r)):
steps += 1
if r[i] == r[j]:
return True, steps
return False, steps
def has_dup_2(r): # remember what we've seen in a set
seen = set()
steps = 0
for x in r:
steps += 1
if x in seen:
return True, steps
seen.add(x)
return False, steps
for n in [10, 100, 1000]:
r = list(range(n)) # no duplicates — the worst case
print(n, has_dup_1(r)[1], has_dup_2(r)[1])
# Output: 10 45 10
# Output: 100 4950 100
# Output: 1000 499500 1000
In the first, steps grow quadratically (n² / 2); in the second, linearly (n). At 1000 items that's 500 times more!
Big-O notation
We describe an algorithm's speed relative to the data size n, dropping small details (½, +1):
| Notation | Name | Example | At n = 1 000 000, roughly |
|---|---|---|---|
| O(1) | constant | r[5] from a list, a key from a dict |
1 step |
| O(log n) | logarithmic | binary search (lesson 2) | 20 steps |
| O(n) | linear | going through a list once | 1 million steps |
| O(n log n) | — | good sorting (sorted) |
20 million steps |
| O(n²) | quadratic | comparing every pair | 1 trillion steps — very slow |
💡 The second solution above is fast because
x in setis O(1) whilex in listis O(n). Choosing the right data structure is the easiest way to speed up an algorithm.
Practice Python
Find the largest number in a list by going through it once (O(n)) — without max(). Also print how many comparisons were made:
eng katta: 42, solishtirish: 5
input() data
Show solution
def eng_katta(r):
katta = r[0]
solishtirish = 0
for x in r[1:]:
solishtirish += 1
if x > katta:
katta = x
return f"eng katta: {katta}, solishtirish: {solishtirish}"
print(eng_katta([7, 42, 3, 19, 42, 8]))