Linear O(n) Algorithms

After a Constant Time Algorithm, and the Logarithmic Algorithms, the linear algorithm, often referred to as an O(n) algorithm in the Big O notation, is the next fastest.

When an algorithm has a time complexity of O(n) the algorithm increases linearly with the size of the input. Inputs are often thought of as an array, or list of elements, but it could also be lines in a file, network data, or something else.

In simpler terms, if you double the size of the input, the algorithm will take roughly twice as long to complete. Likewise, if you have 100 input items being passed to it, it will run 10 times slower than if you have 10 elements. You can easily plot this type of algorithm.

This is in contrast to other types of algorithms, such as quadratic O(n^2) or exponential O(2^n), which can have much faster growth rates.

It would look like a simple line growing at a 45 degree angle as the number of inputs increases. Now if you test this in a real-world scenario, you might find slight variations. This is because your computer has different tasks running in the background. As you test your hypothesis more and more times, the more you’ll see that it is a true line increasing with complexity over a given average number of runs.

If you were to look at a graph comparing different algorithms speed compared to their n sized inputs, the linear algorithm might be a little faster for fewer elements. However, at any real-world scale, it will be slower than the logarithmic algorithms.

With a modern computer, you might not see much change in application speed through a few thousands inputs, depending upon size of the duration set. This is why we measure computation time in milliseconds, on the large side, and micro and nano seconds when we need to be percise.

Characteristics of Linear O(n) Algorithms

• The algorithm visits each element in the input data exactly once. (Think of a brute force style of algorithm.)
• The algorithm performs a constant amount of work for each element.
• The algorithm does not have any nested loops that depend on the size of the input.

Real-World Examples of Linear O(n) Algorithms

1. Finding an Element in an Array: Suppose you have an array of integers and you want to find a specific element. You can iterate through the array, checking each element until you find the one you’re looking for. This is known as a brute force search, and is necessary if you’re working with unsorted data.
2. Counting the Number of Elements in a List: If you have a linked list and you want to count the number of elements, you can iterate through the list, incrementing a counter for each element. This algorithm also has a time complexity of O(n), where ‘n’ is the number of elements in the list.
3. Validating a Credit Card Number: When you enter your credit card number online, the website often checks whether the number is valid. This involves iterating through the digits of the credit card number, performing a calculation for each digit, and checking the result. This algorithm typically has a time complexity of O(n), where ‘n’ is the number of digits in the credit card number. (Most all credit cards have 15 or 16 digits, so this becomes a known quantity.)
4. Reading a File Line by Line: When you read a file line by line, you can process each line as you read it. This involves iterating through the lines of the file, performing some operation for each line. This algorithm has a time complexity of O(n), where ‘n’ is the number of lines in the file.

Example Code

Here is an example of a linear O(n) algorithm in Python, which finds an element in an array:

Python

def find_element(arr, target):
    # step through each element in the list until you find the result
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# Example usage:
arr = [3, 1, 4, 1, 5, 9, 2]
target = 5
index = find_element(arr, target)
print(index)  # Output: 4

This algorithm iterates through the array, checking each element until it finds the target element. The time complexity is O(n), where ‘n’ is the size of the array.

A similar application written in C# might look like:

using System;

class Program
{
    static void Main()
    {
        int[] arr = { 3, 1, 4, 1, 5, 9, 2 };
        int target = 45;

        int index = BruteForceSearch(arr, target);

        if (index != -1)
        {
            Console.WriteLine($"Element found at index: {index}");
        }
        else
        {
            Console.WriteLine("Element not found in the array.");
        }
    }

    static int BruteForceSearch(int[] array, int target)
    {
        // Iterate through each element in the array
        for (int i = 0; i < array.Length; i++)
        {
            // If the target is found, return the index
            if (array[i] == target)
            {
                return i;
            }
        }
        // If the target is not found, return -1
        return -1;
    }
}

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