O with N Raised to a Power Algorithms

You will sometimes see algorithms where in the Big O notation, they are raised to a power, such as O(n²), which is a quadratic algorithm, or O(n³) which is a cubic algorithm.

The time complexity grows pretty quickly with both of these, or any other exponent. You will find that often these types of algorithms use a brute force technique and often the process of nested loops to allow comparisons of all data points to all other data points, but not necessarily.

Let’s look at these in more detail.

The Quadratic O(n²) Algorithm

A quadratic O(n^2) algorithm is a type of algorithm that has a time complexity of O(n²), where ‘n’ represents the number of elements in the input data. This means that the running time of the algorithm increases quadratically with the size of the input.

You will see this in some forms of inefficient sorting algorithms, which will be listed below.

Characteristics of Quadratic O(n²) Algorithms

• The algorithm often involves nested loops that iterate over the input data.
• The algorithm often uses a brute-force approach to solve the problem.
• The algorithm may involve comparing each element in the input data with every other element.

Real-World Examples of Quadratic O(n²) Algorithms

1. Bubble Sort: Bubble sort is a simple sorting algorithm that works by repeatedly iterating through the input data, comparing each pair of adjacent elements and swapping them if they are in the wrong order. The time complexity of bubble sort is O(n^2), making it inefficient for large datasets.
2. Insertion Sort: Insertion sort is another simple sorting algorithm that works by iterating through the input data, inserting each element into its proper position in the sorted portion of the data. The time complexity of insertion sort is O(n^2), although it can perform better than bubble sort for partially sorted data.
3. Finding the Closest Pair of Points: Given a set of points in a two-dimensional space, the closest pair problem involves finding the pair of points that are closest to each other. A brute-force algorithm for solving this problem involves comparing each point with every other point, resulting in a time complexity of O(n^2).

Cubic O(n³) Algorithm Explanation

A cubic O(n^3) algorithm is a type of algorithm that has a time complexity of O(n^3), where ‘n’ represents the number of elements in the input data. This means that the running time of the algorithm increases cubically with the size of the input.

This means it is less efficient than a Quadratic Algorithm. However, you usually won’t find an optimization which easily allows you to move from one point to another.

Characteristics of Cubic O(n³) Algorithms

• The algorithm involves three nested loops that iterate over the input data.
• The algorithm often uses a brute-force approach to solve the problem.
• The algorithm may involve comparing each element in the input data with every other element, and then performing some additional operation.

Real-World Examples of Cubic O(n³) Algorithms

1. Matrix Multiplication: Given two matrices, matrix multiplication involves computing the product of the two matrices. A naive algorithm for matrix multiplication involves iterating over each element of the first matrix, and for each element, iterating over each element of the second matrix, resulting in a time complexity of O(n^3).
2. Finding the Shortest Path in a Weighted Graph: Given a weighted graph, the shortest path problem involves finding the path between two nodes that has the minimum total weight. A brute-force algorithm for solving this problem involves iterating over each possible path between the two nodes, and for each path, computing the total weight, resulting in a time complexity of O(n^3).

Example Code

Here is an example of a matrix multiplication algorithm in Python, which has a time complexity of O(n^3):

Python

def matrix_multiply(A, B):
    num_rows_A = len(A)
    num_cols_A = len(A[0])
    num_rows_B = len(B)
    num_cols_B = len(B[0])

    if num_cols_A != num_rows_B:
        raise ValueError("Number of columns in A must be equal to number of rows in B")

    C = [[0 for _ in range(num_cols_B)] for _ in range(num_rows_A)]

    for i in range(num_rows_A):
        for j in range(num_cols_B):
            for k in range(num_cols_A):  # or 'num_rows_B'
                C[i][j] += A[i][k] * B[k][j]

    return C


# Example usage:
A = [[1, 2, 3], [4, 5, 6]]
B = [[7, 8], [9, 10], [11, 12]]
C = matrix_multiply(A, B)
print(C)

This algorithm uses three nested loops to iterate over the elements of the input matrices, resulting in a time complexity of O(n^3).

O with N Raised to a Power Algorithms was originally found on Access 2 Learn