Algorithm Complexity
Understanding Big-O Notation Made Easy
Welcome! In this session, we will explore one of the most fundamental concepts in
computer science — how to measure algorithm efficiency. By understanding Big-
O notation, you can write code that is faster, more memory-efficient, and more
scalable.
What Is Algorithm Complexity?
Simple Definition Two Types of Complexity
Algorithm complexity is a way to measure how much resources Time Complexity — how long an algorithm runs
(time and memory) an algorithm needs as the input size grows Space Complexity — how much memory is used
larger.
Both are important, but in everyday practice, time complexity is
more often the main focus.
Why Is Big-O Notation
Important?
÷ Slow Algorithm Fast Algorithm
With 1,000 data points and an With an O(log n) algorithm,
O(n²) algorithm, it takes 1,000,000 data points only take
1,000,000 operations. Imagine if about 20 operations. A huge
the data had 1 million points! difference!
Benchmark Standard
Big-O provides a universal language for comparing algorithm efficiency
without depending on hardware.
Understanding Big-O Notation
Big-O describes the upper bound of growth in execution time relative to the input size n. Here are the most common notations, from fastest
to slowest:
O(1) — Constant
1
Execution time does not change even as the input grows larger.
O(log n) — Logarithmic
2
Time grows very slowly, even for very large inputs.
O(n) — Linear
3
Time grows proportionally with the input size.
O(n log n) — Linearithmic
4
Slightly slower than linear, common in efficient sorting algorithms.
O(n²) — Quadratic
5
Time grows very quickly, avoid for large inputs.
O(2^n) — Exponential
6
Time doubles with every additional input. Grows extremely fast, avoid for any meaningful input size.
O(n!) — Factorial
7
Time grows faster than exponential. Only feasible for very tiny inputs (n ≤ 10). Never use on large data.
Visual Comparison of Big-O
Notice how O(n²) explodes very quickly compared with O(1) and O(log n), which stay low. O(2^n) and O(n!) grow so fast they go off the
chart almost immediately, making them practically unusable for any meaningful input size. This chart shows why choosing the right algorithm
is crucial as data grows.
O(1) and O(log n) — The Speed Champions
O(1) — CONSTANT O(LOG N) — LOGARITHMIC
Example: Array Element Access Example: Binary Search
int arr[] = {10, 20, 30, 40, 50}; // Find 7 in a sorted array
// Langsung akses index ke-2 [1, 3, 5, 7, 9, 11, 13]
int x = arr[2]; // Selalu 1 operasi! ↑ middle=7, FOUND! (1 step)
No matter whether the array contains 10 or 10 million elements, // Array 128 elements→ max 7 steps
accessing an index always takes the same amount of time. Other // Array 1M elements → max 20 steps
examples: stack push/pop, hash table access.
At each step, half the data is immediately discarded. Very
efficient!
O(n) and O(n log n) — Intermediate Level
O(n) — Sum of Array Elements O(n log n) — Closest Pair of Points
int sum = 0; closestPair(points):
for (int i = 0; i < n; i++) { sort points by x-coordinate
sum += arr[i]; divide points into left and right halves
} solve each half recursively
check the strip near the split line
Each element is visited exactly once and added into the total. With n
elements, there are n operations. Example: calculating the total of The data is split into halves repeatedly, which creates the log n part.
values in an array. At each level, all points are still processed in total, giving n work per
level. Together this becomes O(n log n).
O(n²) — Be Careful with Nested
Loops!
Example: Bubble Sort Real Impact
for (int i = 0; i < n; i++) { n = 10
for (int j = 0; j < n-i-1; j++) {
100 operations
if (arr[j] > arr[j+1])
✅
swap(arr[j], arr[j+1]);
}
}
n = 1,000
1 million operations ⚠
Two nested loops each run n times,
resulting in a total of n × n = n²
operations. n = 10,000
100 million operations ❌
Use O(n²) only for small datasets.
For large data, always look for a more
efficient alternative.
O(2^n) — The Exponential Trap
O(2^N) — EXPONENTIAL Real Impact
Example: Recursive Fibonacci
n = 10
int fib(int n) { 1,024 operations ⚠
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
} n = 20
1,048,576 operations
Each call branches into TWO more
❌
calls, and this doubles with every level.
For n=5, there are ~32 calls. For n=50,
n = 50
there are over 1 quadrillion calls!
1,125,899,906,842,624 operations
Ê
Even modern computers cannot
handle O(2^n) for inputs beyond ~50.
Always look for dynamic programming
or memoization to reduce it to O(n).
Y Never use naive recursion
for problems like Fibonacci,
subset generation, or the
Traveling Salesman Problem
on large inputs. The
exponential blowup will crash
your program.
Big-O Comparison Summary
The table below summarizes all the Big-O notations we've learned, including exponential and factorial complexity, along with algorithm
examples and performance ratings:
Notation Name Algorithm Example n = 1,000 operations Performance
O(1) Constant Array access, Hash table 1 ⭐ ⭐ ⭐ ⭐ ⭐ Best
O(log n) Logarithmic Binary Search, BST ~10 ⭐ ⭐ ⭐ ⭐ Very Good
O(n) Linear Linear Search, traversal 1,000 ⭐ ⭐ ⭐ Good
O(n log n) Linearithmic Merge Sort, Quick Sort ~10,000 ⭐ ⭐ Fair
O(n²) Quadratic Bubble Sort, Selection Sort 1,000,000 ⭐ Avoid (large data)
O(2^n) Exponential Recursive Fibonacci, 2^1000 ( ∞ practically) Ê Avoid always
Subset generation
O(n!) Factorial Permutation generation, 1000! (beyond ☠ Never use
Brute-force TSP astronomical)
Asymptotic Analysis
Asymptotic analysis is the method of describing the behavior of an algorithm as the input size grows toward infinity. It focuses on the
dominant term and ignores constants and lower-order terms.
Drop Constants // Before simplification:
T(n) = 3n² + 5n + 12
O(2n) simplifies to O(n). Constants don't matter at scale.
// After asymptotic simplification:
O(n²) ← only the dominant term remains
Drop Lower-Order Terms
O(n² + n) simplifies to O(n²). The dominant term wins. Asymptotic analysis lets us compare algorithms fairly, regardless
of hardware or implementation details.
Focus on the Worst Case
Unless stated otherwise, Big-O always describes the upper bound
(worst case).
Best, Average & Worst Cases
Every algorithm can be analyzed under three different scenarios depending on the input. Understanding all three gives a complete picture of
performance.
Ω (OMEGA) — BEST CASE Θ (THETA) — AVERAGE CASE O (BIG-O) — WORST CASE
Ā Best Case ÿ Average Case Û Worst Case
The minimum number of operations The expected number of operations for a The maximum number of operations
needed. This happens when the input is in random input. Most realistic measure of needed. This is what Big-O notation typically
the most favorable condition. real-world performance. describes — the upper bound.
Example — Linear Search: Example — Linear Search: Example — Linear Search:
Target is the first element → only 1 Target is somewhere in the middle → n/2 Target is the last element or not found →n
comparison needed. comparisons on average. comparisons.
Notation: Ω(1) Notation: Θ(n) Notation: O(n)
Algorithm Best Case Average Case Worst Case
Linear Search Ω(1) Θ(n) O(n)
Binary Search Ω(1) Θ(log n) O(log n)
Bubble Sort Ω(n) Θ(n²) O(n²)
Quick Sort Ω(n log n) Θ(n log n) O(n²)
⚠ To ensure system reliability, we should look beyond optimistic performance metrics. Evaluating algorithms based on their average
and worst-case behavior provides a more comprehensive understanding of their scalability and stability.
Key Points to Remember
Choose algorithms based on data size
For small data, O(n²) may be enough. For large data, always use O(n log n)
or better.
Big-O is not the only metric
Also consider hidden constants, space complexity, and ease of
implementation in real-world contexts.
Practice recognizing patterns
One loop = O(n). Two nested loops = O(n²). Halving each iteration = O(log n).
Recognize these patterns!
Profiling > Assumptions
Always measure code performance in practice. Big-O theory is a guide, not
an absolute guarantee in the real world.
D Study Tip: Every time you write code, make a habit of asking: "What is
the complexity of this algorithm?" — This habit will make you a much
better programmer!