Algorithms 101: Big O Notation

Big O Notation

Big O notation is a mathematical notation used to describe the upper limit of the runtime of an algorithm as a function of the input size.

# Example functions to demonstrate Big O notation

# O(1) - Constant Time
def constant_time_example(arr):
    return arr[0]  # Accessing the first element is always O(1)

# O(n) - Linear Time
def linear_time_example(arr):
    for i in arr:
        print(i)  # Printing all elements takes O(n) time

# O(n^2) - Quadratic Time
def quadratic_time_example(arr):
    for i in arr:
        for j in arr:
            print(i, j)  # Printing all pairs takes O(n^2) time

# Example usage
example_array = [1, 2, 3, 4, 5]
constant_result = constant_time_example(example_array)
print(f"Constant time example result: {constant_result}")

print("Linear time example:")
linear_time_example(example_array)

print("Quadratic time example:")
quadratic_time_example(example_array)

Code Explanation

1. Constant Time – O(1): The function constant_time_example accesses the first element of the list, which takes constant time regardless of the list size.

2. Linear Time – O(n): The function linear_time_example iterates through all elements of the list, making its runtime proportional to the list size.

3. Quadratic Time – O(n^2): The function quadratic_time_example iterates through all pairs of elements in the list, resulting in a runtime proportional to the square of the list size.

4. Example Usage: We create an example list and demonstrate the usage of each function to illustrate their respective Big O notations.

Time Complexity

Time complexity is a computational complexity that describes the amount of time it takes to run an algorithm.

# Example functions to demonstrate time complexity

# O(1) - Constant Time
def constant_time_example(arr):
    return arr[0]  # Accessing the first element is always O(1)

# O(n) - Linear Time
def linear_time_example(arr):
    for i in arr:
        print(i)  # Printing all elements takes O(n) time

# O(n^2) - Quadratic Time
def quadratic_time_example(arr):
    for i in arr:
        for j in arr:
            print(i, j)  # Printing all pairs takes O(n^2) time

# Example usage
example_array = [1, 2, 3, 4, 5]
constant_result = constant_time_example(example_array)
print(f"Constant time example result: {constant_result}")

print("Linear time example:")
linear_time_example(example_array)

print("Quadratic time example:")
quadratic_time_example(example_array)

Code Explanation

1. Constant Time – O(1): The function constant_time_example accesses the first element of the list, which takes constant time regardless of the list size.

2. Linear Time – O(n): The function linear_time_example iterates through all elements of the list, making its runtime proportional to the list size.

3. Quadratic Time – O(n^2): The function quadratic_time_example iterates through all pairs of elements in the list, resulting in a runtime proportional to the square of the list size.

4. Example Usage: We create an example list and demonstrate the usage of each function to illustrate their respective time complexities.

Space Complexity

Space complexity is a measure of the amount of working storage an algorithm needs.

# Example functions to demonstrate space complexity

# O(1) - Constant Space
def constant_space_example(n):
    count = 0  # Uses a constant amount of space
    for i in range(n):
        count += 1
    return count

# O(n) - Linear Space
def linear_space_example(n):
    arr = []  # Uses space proportional to n
    for i in range(n):
        arr.append(i)
    return arr

# O(n^2) - Quadratic Space
def quadratic_space_example(n):
    matrix = [[0] * n for _ in range(n)]  # Uses space proportional to n^2
    for i in range(n):
        for j in range(n):
            matrix[i][j] = i + j
    return matrix

# Example usage
n = 5
constant_result = constant_space_example(n)
print(f"Constant space example result: {constant_result}")

linear_result = linear_space_example(n)
print("Linear space example result:", linear_result)

quadratic_result = quadratic_space_example(n)
print("Quadratic space example result:", quadratic_result)

Code Explanation

1. Constant Space – O(1): The function constant_space_example uses a fixed amount of space, regardless of the input size.

2. Linear Space – O(n): The function linear_space_example uses space proportional to the input size n. It creates a list of size n.

3. Quadratic Space – O(n^2): The function quadratic_space_example uses space proportional to the square of the input size. It creates an n x n matrix.

4. Example Usage: We demonstrate the usage of each function to illustrate their respective space complexities.

Here are the common time complexities from smallest to largest, along with examples to illustrate each:

1. O(1) – Constant Time

   • Example: Accessing a specific element in an array.

     def get_first_element(arr):
      return arr[0]

   • Explanation: No matter how large the array is, accessing the first element always takes the same amount of time.

2. O(log n) – Logarithmic Time

   • Example: Binary search in a sorted array.

     def binary_search(arr, target):
      low, high = 0, len(arr) - 1
      while low <= high:
          mid = (low + high) // 2
          if arr[mid] == target:
              return mid
          elif arr[mid] < target:
              low = mid + 1
          else:
              high = mid - 1
      return -1

   • Explanation: Each step reduces the search space by half, leading to a logarithmic number of steps.

3. O(n) - Linear Time

   • Example: Finding the maximum element in an array.

     def find_max(arr):
      max_val = arr[0]
      for num in arr:
          if num > max_val:
              max_val = num
      return max_val

   • Explanation: The function goes through each element once, so the time grows linearly with the size of the array.

4. O(n log n) - Linearithmic Time

   • Example: Merge sort algorithm.

     def merge_sort(arr):
      if len(arr) > 1:
          mid = len(arr) // 2
          L = arr[:mid]
          R = arr[mid:]
     
          merge_sort(L)
          merge_sort(R)
     
          i = j = k = 0
     
          while i < len(L) and j < len(R):
              if L[i] < R[j]:
                  arr[k] = L[i]
                  i += 1
              else:
                  arr[k] = R[j]
                  j += 1
              k += 1
     
          while i < len(L):
              arr[k] = L[i]
              i += 1
              k += 1
     
          while j < len(R):
              arr[k] = R[j]
              j += 1
              k += 1

   • Explanation: Each merge operation is linear, but it takes log n such operations, resulting in O(n log n) time complexity.

5. O(n^2) - Quadratic Time

   • Example: Bubble sort algorithm.

     def bubble_sort(arr):
      n = len(arr)
      for i in range(n):
          for j in range(0, n-i-1):
              if arr[j] > arr[j+1]:
                  arr[j], arr[j+1] = arr[j+1], arr[j]

   • Explanation: There are two nested loops, each going through the array, leading to n * n = n^2 operations.

6. O(n^3) - Cubic Time

   • Example: Naive matrix multiplication.

     def matrix_multiply(A, B):
      n = len(A)
      C = [[0] * n for _ in range(n)]
      for i in range(n):
          for j in range(n):
              for k in range(n):
                  C[i][j] += A[i][k] * B[k][j]
      return C

   • Explanation: Three nested loops each going through n elements lead to n n n = n^3 operations.

7. O(2^n) - Exponential Time

   • Example: Solving the Towers of Hanoi problem.

     def towers_of_hanoi(n, source, target, auxiliary):
      if n == 1:
          print(f"Move disk 1 from {source} to {target}")
          return
      towers_of_hanoi(n-1, source, auxiliary, target)
      print(f"Move disk {n} from {source} to {target}")
      towers_of_hanoi(n-1, auxiliary, target, source)

   • Explanation: Each function call generates two more calls, leading to 2^n operations for n disks.

8. O(n!) - Factorial Time

   • Example: Generating all permutations of a string.

     def permutations(string):
      if len(string) == 1:
          return [string]
      perm_list = []
      for char in string:
          sub_permutations = permutations(string.replace(char, '', 1))
          for perm in sub_permutations:
              perm_list.append(char + perm)
      return perm_list

   • Explanation: There are n! permutations for a string of length n, leading to factorial growth in operations.

These examples illustrate how different time complexities affect the running time of algorithms as the input size grows.

Recommend Resources:

Big-O Notation - For Coding Interviews NeetCode

1.5.1 Time Complexity #1 Abdul Bari