Comparing Functions Mathematically

Understanding how different functions behave as input values grow is fundamental in computer science, especially in analyzing algorithm efficiency. This tutorial walks you through how to compare functions, understand their rates of growth, and use Big-O notation to describe their behavior concisely.

1. Comparing Simple Functions

Let’s begin by considering two simple functions:

f(n)=n
g(n)=n²

We want to observe how their values change as nnn increases.

Step-by-Step Observation

Case 1: f(n)=n

f(100)=100
f(101)=101
f(102)=102
f(103)=103

We can see that for every increase in n by 1, the output also increases by 1. The function grows linearly.

Case 2: g(n)=n²

g(100)=10,000
g(101)=10,201
g(102)=10,404
g(103)=10,609

Here, each increment in n results in a larger jump in output. For example:

From g(100) to g(101): Increase = 201
From g(101) to g(102): Increase = 203

This tells us that g(n)=n² grows faster than f(n)=n.

Conclusion

Different functions grow at different rates. As n→∞n, the values of g(n)=n² grow significantly faster than f(n)=n.

2. Comparing Function Orders: Constants vs Growth

Let’s now consider two more functions:

t1(n)=2n²
t2(n)=99n

At first glance, t2(n) may seem larger for small values of n, especially because 99 is a large constant.

Compare at n=50:

t₁(50)=2×50²=5000
t₂(50)=99×50=4950

Very close! But now try with a much larger constant in t₂(n):

t₂(n)=1,000,000n

Still, as n→∞, t₁(n)=2n² will eventually surpass any linear function due to its higher order of growth.

Key Insight

Constants affect performance for small nnn.
For large nnn, the order (or degree) of the function dominates.
That’s why in asymptotic analysis, we often ignore constants.

3. Understanding Function Orders

Function order refers to how fast a function grows relative to its input. Here’s a table of common function orders, sorted from fastest to slowest growth as n→∞:

Order	Example
n!	Factorial
$n^2$	Exponential
$n^3,n^2$	Polynomial
n log n	Quasilinear
n	Linear
$\sqrt{n}$	Root
log n	Logarithmic
1	Constant

You can visually compare these with graphing tools. For example:

At n=10, n!=3,628,800, while n²=100
Growth differs drastically as n increases

4. Leading Term and Dominance

Consider a complex function:

$T(n) = 5n^2 + 1,000,000n + 5,000,000\sqrt{n}$

Here, each term grows differently:

$5n^2: Polynomial (degree 2)$
1,000,000n: Linear
$5,000,000\sqrt{n}:Root$

When n=1,000,000,000, the term 5n² dominates, even though the other terms have huge constants.

This gives us an important rule:

The term with the highest order (fastest growth rate) is called the leading term. It determines the asymptotic behavior of the function.

5. Identifying Leading Terms Using the Order Table

Let’s practice identifying leading terms.

Given:

$t(n)=n^2 + 2^n$ → Leading term: 2ⁿ
$t(n) = 9n + 5$ → Leading term: 9n
$t(n) = n log n + \sqrt{n}$ → Leading term: n log⁡ n
$t(n) = 6n^3 + n^2$ → Leading term: 6n³

Always choose the term with the highest order from the table.

6. Comparing Functions by Leading Terms

Once we find the leading terms, we can compare functions more easily.

Case A: Different Orders

Compare:

$t_1(n) = 2n^2$
$t_2n=5n$

Here, t₁ grows faster because quadratic functions grow faster than linear ones.

Case B: Same Order

Compare:

$t_1n = 3n$
$t_1n = 7n$

Both are linear, but t₁n grows slower due to its smaller constant.

7. Summary: How to compare functions as n→∞

Find the leading term of each function.
Determine the order of each leading term using the order table.
Compare the orders:
- If orders differ → the function with lower order grows slower.
- If orders are same → compare constants.
Ignore lower-order terms and constants for large nnn analysis.