Big O Notation

Big O Notation: Big O Notation describes the upper bound of an algorithm's runtime or space requirements relative to input size (n). It compares algorithm efficiency by focusing on growth rates, ensuring scalability and optimal performance as input sizes increase.

Here's a brief pseudocode example to illustrate how Big O Notation might be used to compare two sorting algorithms, Bubble Sort and Merge Sort, based on their time complexities.

Bubble Sort (O(n^2))

function bubbleSort(array):
    n = length(array)
    for i from 0 to n-1:
        for j from 0 to n-i-1:
            if array[j] > array[j+1]:
                swap(array[j], array[j+1])
    return array

Merge Sort (O(n log n))

function mergeSort(array):
    if length(array) <= 1:
        return array

    middle = length(array) / 2
    leftHalf = array[0:middle]
    rightHalf = array[middle:]

    return merge(mergeSort(leftHalf), mergeSort(rightHalf))

function merge(left, right):
    result = []
    while left is not empty and right is not empty:
        if left[0] <= right[0]:
            append result with left[0]
            remove first element from left
        else:
            append result with right[0]
            remove first element from right

    while left is not empty:
        append result with left[0]
        remove first element from left

    while right is not empty:
        append result with right[0]
        remove first element from right

    return result

Comparison
Bubble Sort: Nested loops result in O(n^2) time complexity, which means its performance degrades significantly as the input size increases.
Merge Sort: Divides the array into halves and merges sorted halves, resulting in O(n log n) time complexity, which is more efficient for larger inputs.
These examples clearly demonstrate how Big O notation helps in effectively understanding and comparing the efficiency of different algorithms.