Big O Notation Practice Problems with Solutions

 

Big O notation describes how the running time or space requirements of an algorithm grow as the input size n increases. This guide contains Big O practice problems ranging from beginner to advanced, with step-by-step solutions and explanations.

 

Big O notation? Big O notation describes how the running time or space requirements of an algorithm grow as the input size n increases. This guide contains Big O practice problems ranging from beginner to advanced, with step-by-step solutions and explanations.

Complexity	Common example
O(1)	Array access
O(log n)	Binary search
O(n)	Linear search
O(n log n)	Merge sort
O(n²)	Nested loops
O(2ⁿ)	Some recursive algorithms

O(1) O(log n) O(n) O(n log n) O(n²) O(2ⁿ)

n = 64 : (1, log₂n, n) = (1, 6, 64)

(n log₂n, n²) = (384, 4,096)

2ⁿ = 1.84 × 10¹⁹

n

4 8 16 32 64

Problem 1: Constant Time O(1)

bool checkEven(int n) {
    return n % 2 == 0;
}

def check_even(n):
  return n % 2 == 0

Question: What is the time complexity?

Solution: O(1)

Explanation: “Inside the function, a constant number of operations is performed: the modulus operation (% 2) and a comparison (== 0). The number of operations does not depend on the size of the input numbum (n).

Problem 2: Linear Time O(n)

#include 
#include 

void printItems(const std::vector& arr) {
    for (int item : arr) {
        std::cout << item << "\n";
    }
    for (int item : arr) {
        std::cout << item << "\n";
    }
}

def print_items(arr):
  for item in arr:
    print(item)
  for item in arr:
    print(item)

Question: What is the time complexity?

Solution: O(n)

Explanation: The function loops through the list of n elements twice. This gives 2n steps. Big O notation drops constant coefficients, so 2n simplifies to O(n).

Problem 3: Logarithmic Time (O(log n))

int i = 1;
while (i < n) {
    i = i * 2;
}

i = 1
while i < n:
  i = i * 2

Question: What is the time complexity?

Solution: \(O(\log n)\)

Explanation: The complexity is \(O(\log n)\) because the variable i doubles in each iteration, scaling logarithmically relative to n.

Problem 4: Quadratic Time O(n²)

#include 

int findPairs(const std::vector& numbers, int target_sum) {
    int count = 0;
    int n = numbers.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (numbers[i] + numbers[j] == target_sum) {
                count++;
            }
        }
    }
    return count;
}

def find_pairs(numbers, target_sum):
  count = 0
  for i in range(len(numbers)):
    for j in range(len(numbers)):
      if numbers[i] + numbers[j] == target_sum:
        count += 1
  return count