Growth Function
Published by: Anil K. Panta
What is the Order of Growth in Algorithms?
When we write a program or use an algorithm to solve a problem, we want to know:
How fast will it work when the input gets bigger?
That’s where Order of Growth comes in! It helps us understand how quickly an algorithm gets slower or faster as the input size increases.
What is the Order of Growth?
Order of Growth is a way to measure the speed of an algorithm based on the size of input (n).
It tells us how much time or steps an algorithm will take when the input becomes very large.
Think of it like this:
If you're walking, biking, or flying somewhere—flying will get you there faster.
Order of Growth compares "how fast" different algorithms reach the answer.
Examples:
Example 1:
f(n) = 1000
g(n) = n + 1
When n becomes very large (like 1000 or more),
g(n) becomes bigger than f(n) because it grows with n, but f(n) is just a number (constant).
So, g(n) grows faster than f(n).
Example 2:
f(n) = 4n²
g(n) = 2n + 2000
Here, f(n) is a square function (n²) which means it grows faster than g(n) when n becomes big.
How to Quickly Find the Order of Growth?
Just follow these 2 simple steps:
Step 1: Ignore Lower-Order Terms
Ignore the smaller parts like just "n" or constants when there’s a bigger term like n² or n log n.
Step 2: Ignore Constants
If you have 4n², just treat it as n². Constants like 4 or 100 don’t matter for large inputs.
Examples:
Example 1: 4n² + 3n + 100
Step 1: Ignore 3n and 100 → 4n²
Step 2: Ignore 4 → Final Answer: n²
Order of Growth is n²
Example 2: 100n log n + 3n + 2
Step 1: Ignore 3n and 2 → 100n log n
Step 2: Ignore 100 → Final Answer: n log n
Order of Growth is n log n
How to Compare Two Orders of Growth?
Some algorithms grow very slowly, while others grow very fast. Here's a simple chart you can remember:
Constant < log(log n) < log n < √n < n < n log n < n² < n³ < 2ⁿ < nⁿ
The further to the right 👉, the faster the algorithm grows, and the slower it becomes for large input.
Summary:
Final Thought:
Learning Order of Growth helps you choose the best algorithm—one that is fast, efficient, and works well even with big data.
