WebsiteLogo

Time Complexity Analysis and Big O Notation

Understanding and applying Big O notation to analyze the time complexity of algorithms. Learn to estimate the runtime of your code.

⬅ Previous Next ➡

Time Complexity Analysis and Big O Notation in Competitive Programming (Java)

In competitive programming, writing correct code is only half the battle. You also need to ensure your code runs within the given time limit. Understanding time complexity and Big O notation is crucial for estimating the runtime of your algorithms and choosing the most efficient solution. This guide provides a comprehensive explanation of these concepts, along with Java examples and solutions relevant to competitive programming.

Understanding Time Complexity Analysis

Time complexity analysis focuses on how the runtime of an algorithm grows as the input size increases. We're not interested in exact execution times (which depend on the hardware), but rather the *rate* at which the runtime increases. This is particularly important when dealing with large datasets, as small differences in complexity can lead to significant performance differences.

We generally analyze the worst-case scenario, meaning we look at the input that would make the algorithm take the longest to complete.

Big O Notation Explained

Big O notation provides a way to express the upper bound of an algorithm's time complexity. It describes the limiting behavior of a function when the argument tends towards infinity. In simpler terms, it tells us how the runtime scales as the input size becomes very large. It focuses on the dominant term and ignores constant factors and lower-order terms because they become insignificant as the input grows.

Common Time Complexities (Fastest to Slowest)

  • O(1): Constant Time - The algorithm takes the same amount of time regardless of the input size.
  • O(log n): Logarithmic Time - The runtime grows logarithmically with the input size. This is common in algorithms that divide the problem into smaller parts repeatedly (e.g., binary search).
  • O(√n): Square Root Time
  • O(n): Linear Time - The runtime grows linearly with the input size. This is typical when you need to process each element of the input once (e.g., iterating through an array).
  • O(n log n): Linearithmic Time - Often found in efficient sorting algorithms (e.g., merge sort, heap sort).
  • O(n2): Quadratic Time - The runtime grows proportionally to the square of the input size. This is common in nested loops where you compare each element with every other element (e.g., bubble sort, insertion sort).
  • O(n3): Cubic Time
  • O(2n): Exponential Time - The runtime doubles with each addition to the input size. This is often seen in recursive algorithms that explore all possible combinations (e.g., brute-force solutions for some problems).
  • O(n!): Factorial Time - The runtime grows very rapidly. Often associated with generating all permutations of a set.

Examples

O(1) - Constant Time

 public int getFirstElement(int[] arr) {
    return arr[0]; // Accessing the first element takes the same time regardless of the array size.
}

O(n) - Linear Time

 public int sumArray(int[] arr) {
    int sum = 0;
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i]; // Adding each element takes constant time, repeated n times.
    }
    return sum;
}

O(n2) - Quadratic Time

 public void printPairs(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            System.out.println("(" + arr[i] + ", " + arr[j] + ")"); // Nested loops, n * n operations.
        }
    }
}

O(log n) - Logarithmic Time (Binary Search)

 public int binarySearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2; // To prevent overflow
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1; // Not found
}

Each iteration of the while loop effectively halves the search space.

O(n log n) - Linearithmic Time (Merge Sort)

 public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

public void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int[] leftArray = new int[n1];
    int[] rightArray = new int[n2];

    for (int i = 0; i < n1; ++i)
        leftArray[i] = arr[left + i];
    for (int j = 0; j < n2; ++j)
        rightArray[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArray[i] <= rightArray[j]) {
            arr[k] = leftArray[i];
            i++;
        } else {
            arr[k] = rightArray[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = leftArray[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = rightArray[j];
        j++;
        k++;
    }
}

Divide and conquer approach. Dividing takes log(n), merging takes n, total is n log n

Understanding and Applying Big O Notation to Analyze Time Complexity

Analyzing the time complexity of an algorithm involves identifying the operations that are performed repeatedly and determining how many times they are executed in relation to the input size. Here's a step-by-step approach:

  1. Identify the Input Size (n): What parameter determines the scale of the problem (e.g., array length, number of nodes in a graph)?
  2. Identify Basic Operations: What are the fundamental operations performed by the algorithm (e.g., comparison, assignment, arithmetic operation)?
  3. Count Operations: Determine how many times each basic operation is executed as a function of the input size (n).
  4. Find the Dominant Term: Identify the term that grows the fastest as n increases. This term determines the Big O complexity.
  5. Drop Constants and Lower-Order Terms: Simplify the expression by removing constant factors and lower-order terms.

Example Analysis

Consider the following code snippet: 

 public int calculateSum(int[] arr) {
    int sum = 0;  // O(1) - Constant time
    for (int i = 0; i < arr.length; i++) { // O(n) - Loop executes n times
        sum += arr[i];  // O(1) - Constant time operation inside the loop
    }
    return sum;  // O(1) - Constant time
}

Analysis:

  • Input size: n (length of the array)
  • Operations:
    • Initialization: int sum = 0; (O(1))
    • Loop: for (int i = 0; i < arr.length; i++) (O(n))
    • Addition: sum += arr[i]; (O(n))
    • Return: return sum; (O(1))
  • Total Time: O(1) + O(n) + O(n) + O(1) = O(2n + 2)
  • Dominant term: 2n
  • Big O: O(n) (We drop the constant 2)

Estimating the Runtime of Your Code

Competitive programming problems typically have time limits, usually around 1-2 seconds. You can use Big O notation to estimate whether your code will run within the time limit. A common rule of thumb is that a computer can perform approximately 108 operations per second.

Here's how to use this information:

  1. Determine the Input Size (n): Read the problem constraints to find the maximum possible input size.
  2. Determine the Time Complexity (Big O): Analyze your algorithm to determine its Big O complexity.
  3. Estimate the Number of Operations: Calculate the approximate number of operations your algorithm will perform for the maximum input size. For example:
    • O(n): If n = 105, then the number of operations is approximately 105.
    • O(n2): If n = 103, then the number of operations is approximately (103)2 = 106.
    • O(n log n): If n = 106, then the number of operations is approximately 106 * log2(106) ≈ 106 * 20 ≈ 2 * 107. (log base 2 of 10^6 is approximately 20)
  4. Compare to the Limit: If the estimated number of operations is less than or equal to 108, your code is likely to run within the time limit. If it's much larger, you'll need to find a more efficient algorithm.

Example

Problem: Given an array of size n (1 <= n <= 105), find the maximum element.

Solution (Java): 

 public int findMax(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

Analysis:

  • Input size: n = 105
  • Time complexity: O(n)
  • Estimated operations: Approximately 105
  • Conclusion: 105 < 108, so the code should run within the time limit.

Competitive Programming Examples with Solutions

Problem: Two Sum

Given an array of integers `nums` and an integer `target`, return *indices of the two numbers such that they add up to `target`*. You may assume that each input would have *exactly* one solution, and you may not use the *same* element twice. You can return the answer in any order.

 public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        // Using a HashMap for O(n) solution
        Map<Integer, Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement)) {
                return new int[] {numMap.get(complement), i};
            } else {
                numMap.put(nums[i], i);
            }
        }
        // In case there is no solution, which the problem says there is not.
        throw new IllegalArgumentException("No two sum solution");
    }

    public static void main(String[] args) {
        TwoSum ts = new TwoSum();
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = ts.twoSum(nums, target);
        System.out.println(Arrays.toString(result));  // Output: [0, 1]
    }
}

Time Complexity: O(n) - We iterate through the array once.

Space Complexity: O(n) - In the worst case, we store all elements in the HashMap.

Problem: Find the Missing Number

Given an array `nums` containing `n` distinct numbers in the range `[0, n]`, return *the only number in the range that is missing from the array*.

 import java.util.Arrays;

public class MissingNumber {

    // O(n) time using Gauss's formula
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int expectedSum = n * (n + 1) / 2;
        int actualSum = 0;
        for (int num : nums) {
            actualSum += num;
        }
        return expectedSum - actualSum;
    }


    public static void main(String[] args) {
        MissingNumber mn = new MissingNumber();
        int[] nums = {3, 0, 1};
        int missing = mn.missingNumber(nums);
        System.out.println("Missing number: " + missing); // Output: Missing number: 2
    }
}

Time Complexity: O(n) - We iterate through the array once.

Space Complexity: O(1) - Constant space.

Problem: Move Zeroes

Given an integer array `nums`, move all `0`'s to the end of it while maintaining the relative order of the non-zero elements.

 import java.util.Arrays;

public class MoveZeroes {

    public void moveZeroes(int[] nums) {
        int nonZeroIndex = 0; // Index to keep track of non-zero elements

        // Iterate through the array
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                // Move non-zero element to the front of the array
                nums[nonZeroIndex] = nums[i];
                nonZeroIndex++;
            }
        }

        // Fill the remaining elements with zeroes
        while (nonZeroIndex < nums.length) {
            nums[nonZeroIndex] = 0;
            nonZeroIndex++;
        }
    }

    public static void main(String[] args) {
        MoveZeroes mz = new MoveZeroes();
        int[] nums = {0, 1, 0, 3, 12};
        mz.moveZeroes(nums);
        System.out.println(Arrays.toString(nums)); // Output: [1, 3, 12, 0, 0]
    }
}

Time Complexity: O(n) - We iterate through the array at most twice.

Space Complexity: O(1) - Constant space.

⬅ Previous Next ➡