Growth rates and asymptotic notation
Analysis of algorithms studies how the resources an algorithm uses, usually time or memory, grow as the input size n grows. Instead of timing a program on one machine, we count the basic operations it performs. That count is a function of n, and we compare functions by how fast they grow.
Python
def count_log(n):
steps = 0
while n > 1:
n //= 2
steps += 1
return steps
def count_linear(n):
steps = 0
for _ in range(n):
steps += 1
return steps
def count_quadratic(n):
steps = 0
for _ in range(n):
for _ in range(n):
steps += 1
return steps
for n in (8, 16, 32):
print(n, count_log(n), count_linear(n), count_quadratic(n))
assert count_log(1024) == 10