B2.4.1 Efficiency of Specific Algorithms and Big O Notation Notes

Understanding Big O Notation

1. Big O Notation is a mathematical notation used to describe the efficiency of an algorithm in terms of its time and space complexity.
2. Time Complexity: Measures how the execution time of an algorithm changes with the size of the input.
3. Space Complexity: Measures how the memory usage of an algorithm changes with the size of the input.

Common Big O Notations

1. O(1) - Constant Time: The number of operations remains the same regardless of input size.
   1. Example: Accessing an element in an array by index.
2. O(n) - Linear Time: The number of operations increases linearly with the input size.
   1. Example: Iterating through an array.
3. O(log n) - Logarithmic Time: The number of operations increases logarithmically as the input size grows.
   1. Example: Binary search.
4. O(n log n) - Log-Linear Time: Common in efficient sorting algorithms like quicksort and mergesort.
5. O(n²) - Quadratic Time: The number of operations increases quadratically with the input size.
   1. Example: Bubble sort, selection sort.
6. O(2ⁿ) - Exponential Time: The number of operations doubles with each additional input element.
   1. Example: Recursive algorithms without memoization, like the naive Fibonacci sequence.
7. O(n!) - Factorial Time: The number of operations grows factorially with the input size.
   1. Example: Permutation generation, the traveling salesman problem.

Calculating Big O Complexity

1. Identify the Basic Operations: Determine the key operations that drive the algorithm's performance.
2. Analyze Loops and Recursion:
   1. Single loop: Typically O(n).
   2. Nested loops: Multiply the complexities (e.g., O(n²) for two nested loops).
   3. Recursion: Analyze the recursive calls and their depth.
3. Ignore Constants and Lower-Order Terms: Focus on the term that grows the fastest as the input size increases.
   1. Example: O(2n + 3) simplifies to O(n).

def linear_search(arr, target):
    # Traverse through all elements in the list
    for i in range(len(arr)):
        if arr[i] == target:   # Match found
            return i
    return -1                  # No match found

# Example usage
numbers = [5, 3, 8, 4, 2]
print(linear_search(numbers, 8))   # Output: 2
print(linear_search(numbers, 7))   # Output: -1

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2   # Find midpoint
        if arr[mid] == target:
            return mid              # Target found
        elif arr[mid] < target:
            left = mid + 1          # Search right half
        else:
            right = mid - 1         # Search left half

    return -1                       # Target not found

# Example usage
numbers = [2, 4, 6, 8, 10, 12, 14]
print(binary_search(numbers, 10))   # Output: 4
print(binary_search(numbers, 5))    # Output: -1

def bubble_sort(arr):
    n = len(arr)
    # Traverse through all array elements
    for i in range(n - 1):
        # Track whether a swap was made
        swapped = False
        for j in range(n - 1 - i):  # reduce comparisons after each pass
            if arr[j] > arr[j + 1]:
                # Swap elements
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # If no swaps occurred → array is sorted
        if not swapped:
            break
    return arr

# Example usage
numbers = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(numbers))
# Output: [11, 12, 22, 25, 34, 64, 90]

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        # Assume the first unsorted element is the minimum
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # Swap the found minimum element with the first unsorted element
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# Example usage
numbers = [64, 25, 12, 22, 11]
print(selection_sort(numbers))
# Output: [11, 12, 22, 25, 64]

Algorithm Choice Based on Scalability

1. Small Datasets: Simpler algorithms like bubble sort or selection sort may be sufficient.
2. Large Datasets: More efficient algorithms like quicksort or mergesort are preferred.
3. Sorted Data: Use binary search for fast retrieval.
4. Unsorted Data: Consider the cost of sorting versus using a linear search.