O(n log n) Algorithms

A linear O(n log n) algorithm is a type of algorithm that has a time complexity of O(n log n), where ‘n’ represents the number of elements in the input data. This means that the running time of the algorithm increases linearly with the size of the input, but with an additional logarithmic factor.

Now many people will confuse this with a Linear or Logarithmic algorithm, however, it is slower than either of these.

Characteristics of Linear O(n log n) Algorithms

• The algorithm often uses a divide-and-conquer approach, where the problem is divided into smaller sub-problems, and each sub-problem is solved recursively.
• The algorithm may involve sorting or searching operations, which have a logarithmic time complexity.

Real-World Examples of Linear O(n log n) Algorithms

1. Merging Two Sorted Lists: When merging two sorted lists, the algorithm must compare elements from both lists and merge them into a single sorted list. This operation has a time complexity of O(n log n), where ‘n’ is the total number of elements in both lists.
2. External Sorting: External sorting is a technique used to sort large datasets that do not fit into memory. The algorithm divides the data into smaller chunks, sorts each chunk, and then merges the sorted chunks into a single sorted file. This operation has a time complexity of O(n log n), where ‘n’ is the total number of elements in the dataset.
3. Fast Fourier Transform (FFT): The FFT is an algorithm used to efficiently calculate the discrete Fourier transform of a sequence. The algorithm has a time complexity of O(n log n), where ‘n’ is the length of the sequence.
4. Sorting Algorithms like Merge Sort and Heap Sort: Many sorting algorithms, such as merge sort and heap sort, have a time complexity of O(n log n). These algorithms are widely used in many applications, including database systems, file systems, and web search engines.

You will notice several sorting algorithms fall into this category, and often the most efficient ways to sort a given list/array of data.

Example Code

Here is an example of a merge sort algorithm in Python, which has a time complexity of O(n log n):

Python

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    return merge(left_half, right_half)


def merge(left, right):
    merged = []
    left_index = 0
    right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    merged.extend(left[left_index:])
    merged.extend(right[right_index:])

    return merged


# Example usage:
arr = [5, 2, 8, 3, 1, 6, 4]
sorted_arr = merge_sort(arr)
print(sorted_arr)

This algorithm uses a divide-and-conquer approach to sort the input array. The time complexity is O(n log n), where ‘n’ is the length of the input array.

O(n log n) Algorithms was originally found on Access 2 Learn