← Back to Home

Module 2: Big O

Module Overview

Learn about Big O notation and how to analyze the complexity of algorithms.

Learning Objectives

Detailed Explanations

Understanding Big O Notation

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science, it's used to classify algorithms according to how their run time or space requirements grow as the input size grows.

Common Big O Complexities

  • O(1) - Constant Time/Space: The algorithm's performance is independent of the input size
  • O(log n) - Logarithmic Time/Space: The algorithm's performance grows logarithmically in relation to the input size
  • O(n) - Linear Time/Space: The algorithm's performance grows linearly with the input size
  • O(n log n) - Linearithmic Time/Space: Common in efficient sorting algorithms
  • O(n²) - Quadratic Time/Space: Common in algorithms with nested iterations over the data
  • O(2^n) - Exponential Time/Space: Often found in brute force algorithms

Time Complexity Analysis

Analyzing time complexity involves determining how the runtime of an algorithm grows as the input size increases.

Constant Time - O(1)

// Accessing an element in an array by index
int value = array[5]; // O(1)

// Checking if a number is even
boolean isEven = (number % 2 == 0); // O(1)

Linear Time - O(n)

// Iterating through an array once
for (int i = 0; i < array.length; i++) {
    System.out.println(array[i]);
} // O(n)

Quadratic Time - O(n²)

// Nested loops
for (int i = 0; i < array.length; i++) {
    for (int j = 0; j < array.length; j++) {
        System.out.println(array[i] + array[j]);
    }
} // O(n²)

Space Complexity Analysis

Space complexity measures the amount of memory an algorithm needs as input size grows.

Constant Space - O(1)

// Using a fixed number of variables
int sum = 0;
for (int i = 0; i < array.length; i++) {
    sum += array[i];
} // O(1) space complexity

Linear Space - O(n)

// Creating a new array of the same size as input
int[] duplicate = new int[array.length];
for (int i = 0; i < array.length; i++) {
    duplicate[i] = array[i];
} // O(n) space complexity

Comparing Algorithm Efficiency

When comparing algorithms that solve the same problem, we analyze both time and space complexity to determine which is more efficient.

For example, when searching for an element:

  • Linear Search: O(n) time complexity - must check each element
  • Binary Search: O(log n) time complexity - more efficient for large sorted datasets

When choosing between algorithms, consider:

  • The size of the input data
  • Available memory resources
  • Performance requirements
  • Implementation complexity

Resources