Big O, Growth, and a Python Experiment
I still remember the first time Big O notation really landed in my mind. Before that, algorithms felt like recipes. You follow the steps, you get the output, done. But in a data structures class, the conversation changed. It was no longer only about does it work? It became how does it grow? What happens when the input is not 10, not 100, but 10,000 or 10,000,000?
That question stayed in my head. And one day, I decided to turn that curiosity into a small experiment, using Python.
The moment I got suspicious
In class, we learn common growth rates:
- constant
- logarithmic
- linear
- n log n
- polynomial
- exponential
- factorial
We memorise them like a ranking ladder. But then the weird ones show up. Things like:
- log star (log* n)
- (log n)!
- (log n)^(log n)
- n^(log log n)
- 2^(2^n)
At that point, my brain started treating them like mythical creatures. I knew their names, but I did not truly feel their size. So I asked myself:
What if I force them all into one arena, pick a value like n = 1000, and see who dominates?
The real challenge: overflow and “numbers too big to exist”
The first problem appeared immediately. If I try to compute 1000! Directly, Python can handle it as an integer, but it becomes enormous. If I try something like 2^(2^1000), it is so huge that it’s basically impossible to store or even represent in normal floating-point numbers. So I needed a trick.
Instead of comparing f(n) directly, I compare:
log10(f(n))
This transforms huge values into something we can safely compare and plot.
- log10(n!) is manageable using the gamma function: lgamma(n+1)
- log10(e^n) is just n * log10(e)
- log10(2^(2^n)) becomes (2^n) * log10(2)
So the story of this code is really the story of avoiding overflow while still respecting the true growth behaviour.
Building the “growth zoo”
I collected a list of functions that appear in algorithm analysis, including classics and unusual ones:
- 1
- ln(n)
- log2(n)
- log* n
- n
- n log n
- n^2
- n^3
- 2^n
- n 2^n
- e^n
- n!
- (n+1)!
- 2^(2^n)
- and others involving log and factorial combinations
Then I wrote two key features:
- Plot all functions on the same chart using log10 scale
- Sort them at n = 1000 from largest to smallest
That sorting result was the part that felt like opening a door.
The ranking at n = 1000
When I ran the comparison, my program produced this ordering:
import math
import numpy as np
import matplotlib.pyplot as plt
LN2 = math.log(2.0)
LN10 = math.log(10.0)
def ln(x: float) -> float:
return math.log(x)
def logb(x: float, b: float) -> float:
return math.log(x) / math.log(b)
def log2(x: float) -> float:
return math.log(x) / LN2
def log10_from_ln(ln_val: float) -> float:
return ln_val / LN10
def safe_float(x):
try:
if x is None:
return float("nan")
x = float(x)
if math.isnan(x) or math.isinf(x):
return float("nan")
return x
except Exception:
return float("nan")
def safe_log10_value(v: float) -> float:
v = safe_float(v)
if math.isnan(v):
return float("nan")
if v <= 0: return float("nan") return math.log10(v) def log_star(n: int, base: float = 2.0) -> int:
if n <= 0: return 0 x = float(n) c = 0 while x > 1.0:
x = logb(x, base)
c += 1
if c > 10000:
return 10000
return c
def log_star_var_base(x0: float, base: float) -> int:
if x0 <= 0 or base <= 1.0: return 0 x = float(x0) c = 0 while x > 1.0:
x = logb(x, base)
c += 1
if c > 10000:
return 10000
return c
def f_log_logstarn(n: int) -> float:
ls = log_star(n, 2.0)
if ls <= 1: return float("nan") return log2(ls) def f_2_pow_logstarn(n: int) -> float:
ls = log_star(n, 2.0)
return 2.0 ** ls
def f_sqrt2_pow_log2n(n: int) -> float:
if n <= 0: return float("nan") return (math.sqrt(2.0) ** log2(n)) def f_n2(n: int) -> float:
return n * n
def f_n_factorial(n: int) -> float:
return float("nan")
def f_log2n_factorial(n: int) -> float:
return float("nan")
def f_const_3over2_pow2(n: int) -> float:
return (3.0 / 2.0) ** 2
def f_n3(n: int) -> float:
return n ** 3
def f_log2_of_n(n: int) -> float:
if n <= 0: return float("nan") return log2(n) def f_log2_of_n_factorial(n: int) -> float:
return float("nan")
def f_2_pow_2_pow_n(n: int) -> float:
return float("nan")
def f_n_pow_1_over_logn_n2(n: int) -> float:
if n <= 0: return float("nan") return math.sqrt(n) def f_ln_ln_n(n: int) -> float:
if n <= 1: return float("nan") return ln(ln(n)) def f_logstarn(n: int) -> float:
return float(log_star(n, 2.0))
def f_n_2_pow_n(n: int) -> float:
return float("nan")
def f_n_pow_log2_log2n(n: int) -> float:
return float("nan")
def f_ln_n(n: int) -> float:
if n <= 0: return float("nan") return ln(n) def f_one(n: int) -> float:
return 1.0
def f_2_pow_log2n(n: int) -> float:
if n <= 0: return float("nan") return float(n) def f_log2n_pow_log2n(n: int) -> float:
return float("nan")
def f_e_pow_n(n: int) -> float:
return float("nan")
def f_4_pow_log2n(n: int) -> float:
if n <= 0: return float("nan") return float(n * n) def f_nplus1_factorial(n: int) -> float:
return float("nan")
def f_logstar_of_log2n_base_log2n(n: int) -> float:
if n <= 1:
return float("nan")
b = log2(n)
if b <= 1.0: return float("nan") x0 = b return float(log_star_var_base(x0, b)) def f_2_pow_sqrt_2log2n(n: int) -> float:
if n <= 0:
return float("nan")
a = log2(n)
if a < 0: return float("nan") return 2.0 ** math.sqrt(2.0 * a) def f_n(n: int) -> float:
if n <= 0: return float("nan") return float(n) def f_2_pow_n(n: int) -> float:
return float("nan")
def f_n_log2n(n: int) -> float:
if n <= 0: return float("nan") return float(n) * log2(n) def f_2_pow_2_pow_n_plus_1(n: int) -> float:
return float("nan")
def L_log_logstarn(n: int) -> float:
v = f_log_logstarn(n)
return safe_log10_value(v)
def L_2_pow_logstarn(n: int) -> float:
ls = log_star(n, 2.0)
return ls * math.log10(2.0)
def L_sqrt2_pow_log2n(n: int) -> float:
if n <= 0: return float("nan") return log2(n) * math.log10(math.sqrt(2.0)) def L_n2(n: int) -> float:
if n <= 0: return float("nan") return 2.0 * math.log10(n) def L_n_factorial(n: int) -> float:
if n < 0: return float("nan") return log10_from_ln(math.lgamma(n + 1.0)) def L_log2n_factorial(n: int) -> float:
if n <= 0:
return float("nan")
x = log2(n)
if x < 0: return float("nan") return log10_from_ln(math.lgamma(x + 1.0)) def L_const_3over2_pow2(n: int) -> float:
return math.log10((3.0 / 2.0) ** 2)
def L_n3(n: int) -> float:
if n <= 0: return float("nan") return 3.0 * math.log10(n) def L_log2_of_n(n: int) -> float:
v = f_log2_of_n(n)
return safe_log10_value(v)
def L_log2_of_n_factorial(n: int) -> float:
if n < 0: return float("nan") v = math.lgamma(n + 1.0) / LN2 return safe_log10_value(v) def L_2_pow_2_pow_n(n: int) -> float:
if n < 0: return float("nan") return (2.0 ** n) * math.log10(2.0) def L_n_pow_1_over_logn_n2(n: int) -> float:
if n <= 0: return float("nan") return 0.5 * math.log10(n) def L_ln_ln_n(n: int) -> float:
v = f_ln_ln_n(n)
return safe_log10_value(v)
def L_logstarn(n: int) -> float:
v = f_logstarn(n)
return safe_log10_value(v)
def L_n_2_pow_n(n: int) -> float:
if n <= 0: return float("nan") return math.log10(n) + n * math.log10(2.0) def L_n_pow_log2_log2n(n: int) -> float:
if n <= 1:
return float("nan")
a = log2(n)
if a <= 0: return float("nan") b = log2(a) return b * math.log10(n) def L_ln_n(n: int) -> float:
v = f_ln_n(n)
return safe_log10_value(v)
def L_one(n: int) -> float:
return 0.0
def L_2_pow_log2n(n: int) -> float:
if n <= 0: return float("nan") return math.log10(n) def L_log2n_pow_log2n(n: int) -> float:
if n <= 1:
return float("nan")
x = log2(n)
if x <= 0: return float("nan") return x * math.log10(x) def L_e_pow_n(n: int) -> float:
return n * math.log10(math.e)
def L_4_pow_log2n(n: int) -> float:
return L_n2(n)
def L_nplus1_factorial(n: int) -> float:
if n < 0: return float("nan") return log10_from_ln(math.lgamma((n + 1) + 1.0)) def L_logstar_of_log2n_base_log2n(n: int) -> float:
v = f_logstar_of_log2n_base_log2n(n)
return safe_log10_value(v)
def L_2_pow_sqrt_2log2n(n: int) -> float:
if n <= 0:
return float("nan")
a = log2(n)
if a < 0: return float("nan") return math.sqrt(2.0 * a) * math.log10(2.0) def L_n(n: int) -> float:
if n <= 0: return float("nan") return math.log10(n) def L_2_pow_n(n: int) -> float:
return n * math.log10(2.0)
def L_n_log2n(n: int) -> float:
if n <= 1:
return float("nan")
a = log2(n)
if a <= 0: return float("nan") return math.log10(n) + math.log10(a) def L_2_pow_2_pow_n_plus_1(n: int) -> float:
return L_2_pow_2_pow_n(n)
FUNCTIONS_LOG10 = [
("log(log* n)", L_log_logstarn),
("2^(log* n)", L_2_pow_logstarn),
("(sqrt(2))^(log2 n)", L_sqrt2_pow_log2n),
("n^2", L_n2),
("n!", L_n_factorial),
("(log2 n)!", L_log2n_factorial),
("(3/2)^2", L_const_3over2_pow2),
("n^3", L_n3),
("log2 n", L_log2_of_n),
("log2(n!)", L_log2_of_n_factorial),
("2^(2^n)", L_2_pow_2_pow_n),
("n^(1/log_n(n^2))", L_n_pow_1_over_logn_n2),
("ln(ln(n))", L_ln_ln_n),
("log* n", L_logstarn),
("n*2^n", L_n_2_pow_n),
("n^(log2(log2 n))", L_n_pow_log2_log2n),
("ln(n)", L_ln_n),
("1", L_one),
("2^(log2 n)", L_2_pow_log2n),
("(log2 n)^(log2 n)", L_log2n_pow_log2n),
("e^n", L_e_pow_n),
("4^(log2 n)", L_4_pow_log2n),
("(n+1)!", L_nplus1_factorial),
("log*(log2 n) base log2 n", L_logstar_of_log2n_base_log2n),
("2^(sqrt(2 log2 n))", L_2_pow_sqrt_2log2n),
("n", L_n),
("2^n", L_2_pow_n),
("n*log2 n", L_n_log2n),
("2^(2^n)+1", L_2_pow_2_pow_n_plus_1),
]
def plot_like_sample(n_values, selected_names, x_axis_n=True, save_path=None):
name_to_fn = {name: fn for name, fn in FUNCTIONS_LOG10}
series = []
labels = []
for nm in selected_names:
if nm not in name_to_fn:
raise ValueError(f"Function name not found: {nm}")
fn = name_to_fn[nm]
ys = []
for n in n_values:
y = fn(int(n))
y = safe_float(y)
if math.isinf(y):
y = float("nan")
ys.append(y)
series.append(np.array(ys, dtype=float))
labels.append(nm)
x = np.array(n_values, dtype=float) if x_axis_n else np.arange(len(n_values))
n_curves = len(series)
figsize = (14, 8) if n_curves > 10 else (10, 6)
plt.figure(figsize=figsize)
for i, y in enumerate(series):
plt.plot(
x, y,
linewidth=1.5,
alpha=0.85,
label=labels[i]
)
plt.grid(True, linestyle="--", alpha=0.35)
plt.xlabel("n (input)" if x_axis_n else "index")
plt.ylabel("log₁₀(f(n))")
plt.title("Plot of Big O functions")
if x_axis_n and len(n_values) > 20:
step = max(1, len(n_values) // 15)
tick_indices = list(range(0, len(n_values), step))
if len(n_values) - 1 not in tick_indices:
tick_indices.append(len(n_values) - 1)
tick_pos = [n_values[i] for i in tick_indices]
plt.xticks(tick_pos, [str(n) for n in tick_pos])
elif not x_axis_n:
plt.xticks(np.arange(len(n_values)), [str(v) for v in n_values])
ncol = 2 if n_curves > 12 else 1
plt.legend(fontsize=7, ncol=ncol, loc="upper left")
plt.tight_layout()
if save_path:
plt.savefig(save_path, dpi=120, bbox_inches="tight")
print(f"plot saved to {save_path}")
else:
plt.show()
def compare_at_n(n=1000):
rows = []
for name, fn in FUNCTIONS_LOG10:
try:
v = safe_float(fn(int(n)))
except OverflowError:
v = float("inf")
rows.append((name, v))
rows.sort(key=lambda t: (math.isnan(t[1]), -(t[1]) if not math.isnan(t[1]) else 0))
print(f"Growth order (from largest to smallest) at n={n}:")
chain = " > ".join(name for name, _ in rows)
print(chain)
if __name__ == "__main__":
n_values = list(range(1, 1000))
selected = [name for name, _ in FUNCTIONS_LOG10]
plot_like_sample(n_values, selected, x_axis_n=True, save_path="big_o_plot.png")
compare_at_n(1000)
Growth order (from largest to smallest) at n=1000:
2^(2^n) > 2^(2^n)+1 > (n+1)! > n! > e^n > n2^n > 2^n > n^(log2(log2 n)) > (log2 n)^(log2 n) > n^3 > (log2 n)! > n^2 > 4^(log2 n) > nlog2 n > log2(n!) > 2^(log2 n) > n > (sqrt(2))^(log2 n) > n^(1/log_n(n^2)) > 2^(sqrt(2 log2 n)) > 2^(log* n) > log2 n > ln(n) > log* n > (3/2)^2 > log(log* n) > ln(ln(n)) > 1 > log*(log2 n) base log2 n
Seeing it like this made the theory feel real. Some things matched my expectations:
- Double exponential dominates everything
- Factorial beats exponential
- Exponential beats polynomial
- Polynomial beats n log n
But some things became more intuitive only after seeing them together. For example:
- 4^(log2 n) is just n^2, so they land in the same neighborhood
- 2^(log2 n) is exactly n, so it sits right on the linear line
- n^(1/log_n(n^2)) simplifies to sqrt(n), which is smaller than n but bigger than log-based growth
It felt like watching all the characters from the textbook finally appear in the same scene.
Why plotting matters
Sorting at one point (like n = 1000) is fun, but plotting shows the full personality of each function.
- Some functions are slow starters but eventually explode.
- Some look scary, but stay small for practical sizes.
- Some are basically invisible compared to others.
That is why the code includes a plot function that draws all curves using log10 values. It is like building a map of growth.
What this taught me
This experiment did not just confirm Big O rankings. It gave me something better:
A sense of scale.
Now when I hear “factorial time” I do not only think “bad.”
I think “it crushes exponentially.”
And when I hear “log star,” I do not only think “tiny.”
I remember it grows so slowly that it barely moves in most real input sizes.
That is the kind of understanding you cannot get from memorising alone.
Appreciation
At the end, I want to appreciate Dr Hadi Yousefi, whose data structures class helped shape how I think about algorithms. Learning Big O notation and the growth of functions in that class gave me the foundation for experiments like this, and it changed the way I look at code forever.
Because after that, writing an algorithm is not only about making it work. It is about understanding how it behaves when the input grows.