DEV Community

mohamed Tayel
mohamed Tayel

Posted on

1

Understanding O(N): Linear Time Complexity in Algorithms

What is O(N)?

In algorithm analysis, O(N), or linear time complexity, indicates that the time an algorithm takes to complete grows proportionally with the size of the input ( N ). If the input size doubles, the execution time also roughly doubles. This is one of the most common and straightforward time complexities in computer science.

Characteristics of O(N):

  • The algorithm processes each element of the input exactly once.
  • The number of operations grows linearly with the input size.
  • Commonly found in problems involving simple iterations over lists, arrays, or collections.

A Simple Example: Finding the Maximum Value in an Array

Problem Statement:

We need to find the largest number in an array of integers. The array can have any size, and the elements are not sorted.

Step-by-Step Breakdown:

  1. Input and Output:

    • Input: An array of integers, e.g., ([2, 8, 3, 7, 4]).
    • Output: The maximum value, e.g., (8).
  2. The Algorithm:

    • Start with a variable max initialized to the smallest possible value (e.g., int.MinValue in C#).
    • Traverse the array from the first to the last element.
    • For each element:
      • Compare it to max.
      • If it’s greater than max, update max.
    • Once the loop completes, max will hold the largest value.

C# Code Implementation:

using System;

class Program
{
    static void Main()
    {
        // Example array
        int[] numbers = { 2, 8, 3, 7, 4 };

        // Call the method to find the maximum value
        int max = FindMaxValue(numbers);

        // Output the result
        Console.WriteLine($"The maximum value is: {max}");
    }

    static int FindMaxValue(int[] numbers)
    {
        int max = int.MinValue; // Start with the smallest possible integer

        // Iterate through the array
        foreach (int number in numbers)
        {
            if (number > max) // Compare the current number with max
            {
                max = number; // Update max if the current number is greater
            }
        }

        return max; // Return the largest value
    }
}
Enter fullscreen mode Exit fullscreen mode

Step-by-Step Execution:

Let’s walk through an example with the array ([2, 8, 3, 7, 4]):

  1. Initialize max = int.MinValue (smallest possible integer).
  2. Compare each element in the array to max:
    • Compare (2) with max ((-2147483648)): Update max to (2).
    • Compare (8) with max ((2)): Update max to (8).
    • Compare (3) with max ((8)): No change.
    • Compare (7) with max ((8)): No change.
    • Compare (4) with max ((8)): No change.
  3. After the loop, max = 8.

Why is This O(N)?

  • The algorithm loops through each element once.
  • Each comparison and update is a constant-time operation ( O(1) ).
  • Therefore, the total time complexity is ( O(N) ), where ( N ) is the number of elements in the array.

Another Example: Summing All Elements in an Array

Problem Statement:

Given an array of integers, calculate the sum of all elements.

Algorithm:

  1. Initialize a variable sum = 0.
  2. Traverse each element of the array.
  3. Add the current element to sum.
  4. After completing the loop, sum will contain the total.

C# Code Implementation:

static int CalculateSum(int[] numbers)
{
    int sum = 0;

    foreach (int number in numbers)
    {
        sum += number; // Add each number to sum
    }

    return sum;
}
Enter fullscreen mode Exit fullscreen mode

Why is This O(N)?

The algorithm iterates through all ( N ) elements once, performing a constant-time addition for each. The time complexity is ( O(N) ).


Common Examples of O(N):

  • Finding a specific element in an unsorted list.
  • Counting occurrences of a specific value in an array.
  • Merging two sorted arrays of size ( N ) and ( M ).
  • Reversing an array or list.

Key Insights:

  • O(N) is efficient for moderately large inputs, but performance can degrade for extremely large inputs.
  • Always aim to minimize unnecessary operations inside the loop to keep performance optimal.

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more