Training Computer Engineering Algorithm Complexity — Big-O Notation
3 / 5

Algorithm Complexity — Big-O Notation

24 min Computer Engineering

Algorithm Complexity — Big-O Notation

Big-O notation describes how an algorithm's running time or space grows as the input size $n$ increases.

Big-O Definition

$f(n) = O(g(n))$ if there exist constants $c > 0$ and $n_0$ such that:

$$f(n) \le c \cdot g(n) \quad \text{for all } n \ge n_0$$

Big-O captures the upper bound on growth rate, ignoring constants and lower-order terms.

Common Complexity Classes
Big-ONameExample
$O(1)$ConstantArray index access
$O(\log n)$LogarithmicBinary search
$O(n)$LinearSimple loop
$O(n \log n)$LinearithmicMerge sort
$O(n^2)$QuadraticNested loops (bubble sort)
$O(2^n)$ExponentialRecursive subset generation
Example 1

What is the Big-O of $f(n) = 3n^2 + 5n + 100$?

Drop constants and lower-order terms: $O(n^2)$.

As $n \to \infty$, the $n^2$ term dominates.

Example 2

A loop runs $n$ times, and inside it another loop runs $n$ times. Within the inner loop, we do $O(1)$ work. What's the total complexity?

$$O(n \times n \times 1) = O(n^2)$$

Example 3

Binary search halves the search space each step. If $n = 1{,}024$, how many steps at most?

$$\log_2 1{,}024 = 10 \text{ steps}$$

Complexity: $O(\log n)$.

Practice Problems

1. What is Big-O of $f(n) = 7n + 3\log n + 42$?
2. A function calls itself twice with input $n/2$. What's the complexity? (Think recursion tree.)
3. What is the time complexity of searching an unsorted array of $n$ elements?
4. Merge sort divides the array in half and merges in $O(n)$. Write the recurrence and state the complexity.
5. If an $O(n^2)$ algorithm takes 1 second for $n = 1{,}000$, how long for $n = 10{,}000$?
6. Rank these in order: $O(n!)$, $O(n^2)$, $O(2^n)$, $O(n \log n)$, $O(1)$, $O(n)$, $O(\log n)$.
7. What is the complexity of accessing element $A[i][j]$ in a 2D array?
8. A hash table lookup is $O(1)$ average. What is the worst case?
9. How many comparisons does bubble sort make for $n$ elements?
10. $\log_2 n = 20$. What is $n$?
11. Master theorem: $T(n) = 2T(n/2) + n$. Find the complexity.
12. An algorithm does $n$ operations, then $n/2$, then $n/4$, etc. Find the total operations and Big-O.
Show Answer Key

1. $O(n)$ — linear term dominates

2. $T(n) = 2T(n/2) + O(1)$ → $O(n)$ by Master theorem (case 1) — similar to traversing a binary tree

3. $O(n)$ — linear scan

4. $T(n) = 2T(n/2) + O(n)$ → $O(n \log n)$

5. $(10{,}000/1{,}000)^2 = 100\times$ slower → 100 seconds

6. $O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n) < O(n!)$

7. $O(1)$ — direct access with index arithmetic

8. $O(n)$ — when all elements hash to the same bucket

9. $n(n-1)/2 = O(n^2)$

10. $n = 2^{20} = 1{,}048{,}576$

11. $O(n \log n)$ — Master theorem case 2

12. Total $= n + n/2 + n/4 + \cdots = 2n$; $O(n)$

Boolean Algebra & Logic Gates Modular Arithmetic & Cryptography Math