Data Structures With C Complexity Analysis And Big O Notation Complete Guide

1. Understanding Complexity Analysis

Complexity Analysis refers to the process of determining the amount of resources (time and space) an algorithm consumes relative to the size of the input.

Key Components:

• Time Complexity: Measures the number of operations an algorithm performs as a function of the input size.
• Space Complexity: Measures the amount of memory an algorithm uses as a function of the input size.

2. Understanding Big O Notation

Big O Notation is used to describe the upper bound or the worst-case scenario of the time or space complexity of an algorithm.

Common Big O Notations:

• (O(1)) - Constant Time
• (O(\log n)) - Logarithmic Time
• (O(n)) - Linear Time
• (O(n \log n)) - Linearithmic Time
• (O(n^2)) - Quadratic Time
• (O(n^3)) - Cubic Time
• (O(2^n)) - Exponential Time
• (O(n!)) - Factorial Time

3. Step-by-Step Examples

Example 1: Constant Time Complexity (O(1))

Description: An algorithm that performs a fixed number of operations regardless of the input size.

def get_element(arr, index):
    return arr[index]

• Explanation:
  • The get_element function always performs a single operation: accessing an element at the specified index.
  • Thus, the time complexity is (O(1)) and the space complexity is (O(1)).

Example 2: Logarithmic Time Complexity (O(\log n))

Description: An algorithm that reduces the problem size by half in each iteration.

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

• Explanation:
  • Binary search halves the search space in each iteration.
  • The number of comparisons is proportional to the logarithm of the input size (n).
  • Therefore, the time complexity is (O(\log n)).

Example 3: Linear Time Complexity (O(n))

Description: An algorithm that processes each element in the input exactly once.

def sum_array(arr):
    total = 0
    for num in arr:
        total += num
    return total

• Explanation:
  • The sum_array function iterates over each element in the input array arr.
  • The number of iterations is directly proportional to the size of the array (n).
  • Therefore, the time complexity is (O(n)).

Example 4: Quadratic Time Complexity (O(n^2))

Description: An algorithm that involves a nested loop, where both loops iterate over the elements in the input.

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]
    return arr

• Explanation:
  • The bubble_sort function contains two nested loops.
  • The outer loop runs (n) times, and the inner loop runs approximately (n/2) times on average.
  • Therefore, the total number of comparisons is (n \times (n/2)), which simplifies to (O(n^2)).

Example 5: Space Complexity (O(n))

Description: An algorithm that uses an additional data structure proportional to the input size.

def copy_array(arr):
    new_arr = []
    for num in arr:
        new_arr.append(num)
    return new_arr

• Explanation:
  • The copy_array function creates a new array new_arr that is a copy of the input array arr.
  • The size of new_arr is the same as the size of arr, which is proportional to (n).
  • Therefore, the space complexity is (O(n)).

Example 6: Amortized Time Complexity (O(1))

Description: An algorithm where the average time complexity per operation is constant, even though individual operations might take more time.

def dynamic_array():
    arr = []
    for i in range(100):
        arr.append(i)
    return arr

• Explanation:
  • Python lists (dynamically sized arrays) double their size when they run out of space.
  • Although individual append operations can take (O(n)) time when resizing occurs, the amortized time complexity per append operation is (O(1)).
  • This is because resizing happens infrequently, and the average number of operations per append remains constant over a sequence of operations.

4. Analyzing Algorithm Complexity Practice

Practice Problem:

Determine the time and space complexity of the following function:

def find_duplicates(arr):
    duplicates = []
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j] and arr[i] not in duplicates:
                duplicates.append(arr[i])
    return duplicates

Solution:

• Time Complexity:

  • The outer loop runs (n) times.
  • The inner loop runs approximately (n/2) times on average for each iteration of the outer loop.
  • Thus, the total number of comparisons is (n \times (n/2)), which simplifies to (O(n^2)).

• Space Complexity:

  • The duplicates list can hold up to (n/2) elements in the worst case (if all elements are unique except for one duplicate).
  • Therefore, the space complexity is (O(n)).