Linear (O(n))

At a glance: The amount of work or auxiliary storage grows in direct proportion to the number of elements.

Jump to: Time complexity · Space complexity · Try it yourself

Understand the growth

Imagine checking every item on a shelf until you find a matching label. If there is no shortcut or index, doubling the number of items can double the number of comparisons required in the worst case.

A loop that performs one constant-cost operation for each of n elements has T(n) = a·n + b for constants a and b. Big O drops these constant factors, leaving O(n). An O(n) upper bound does not mean every execution necessarily visits every element.

Why a complete scan is linear

When a search must inspect entries in an unsorted array and has no additional index, any entry might contain the target. An unsuccessful search must examine every one of the n entries to be sure the target is absent. The worst-case number of comparisons therefore grows with n, which gives Θ(n) time for the simple linear-search example.

A one-pass operation need not be a search. Computing a checksum over a list, counting how many scores exceed a threshold, or writing one result per input element all require work tied to the number of elements. If each element costs a bounded constant amount of work, two passes still take Θ(n), since 2n is the same asymptotic class as n.

Be precise about the measured size: an array of n fixed-width integers is a natural model. If entries are strings of different lengths, comparing a target to an entry may cost more than one constant step; the sum of string lengths may be a more useful input measure.

Worked example

A full scan of 50 entries makes at most 50 element checks; a full scan of 100 makes at most 100. A copy of 100 fixed-size integers stores roughly twice as many copied element bytes as a copy of 50.

Trace a target at different positions

Search for 8 in [8, 4, 6, 2, 1]: the first comparison succeeds, so the best-case work is one comparison. Search for 1 and five comparisons are required. Search for 99 and the loop also examines all five entries before returning -1. If the data grows to 50 entries, a failed lookup now requires 50 comparisons, ten times as many.

If you know every target is equally likely to occur once at one of n positions, the expected number of comparisons for a successful search is (n + 1)/2. That is still Θ(n). Such an average-case statement depends on the assumed distribution; it is not automatically valid for arbitrary workloads.

Time complexity

Representative time example: Scanning each element once.

Linear search compares each array entry with the target and returns the first matching index. If the target is first, the best case is O(1). If it is last or absent, the algorithm examines all n entries, giving O(n) worst-case time. Average-case claims require a distribution of targets and positions. For unsorted input, a binary search is not a drop-in replacement because the sorted-order precondition is missing.

Recognize early exits and hidden work

The search examines indices in increasing order and stops immediately on a match. It never revisits an index, so it performs at most n equality checks. The best case is Θ(1); the worst case is Θ(n). If you change the body to run a second scan for every element, the work may rise to Θ(n²) even though the outer loop is still a single visible loop.

By contrast, a for loop that takes steps of two still visits about half the elements and remains Θ(n). A loop that repeatedly halves its remaining range is different because it performs only logarithmically many iterations. Analyze how the loop variable changes, not merely whether the source contains a loop.

C#

C# | Linear.cs

int Find(int[] values, int target)
{
    for (int i = 0; i < values.Length; i++)
        if (values[i] == target) return i;
    return -1;
}

C++

C++ | linear.cpp

#include <vector>

int findIndex(const std::vector<int>& values, int target) {
    for (std::size_t i = 0; i < values.size(); ++i)
        if (values[i] == target) return static_cast<int>(i);
    return -1;
}

Analysis: Worst-case O(n) time, best-case O(1) when the target is first.

The C++ version illustrates the same operation. The container, compiler and any functions called by the example still matter when analyzing a complete program.

Space complexity

Representative memory example: Copying an array.

Copying an array produces a second array with n elements, so it needs O(n) auxiliary space as long as both input and copy are present. The act of copying also takes O(n) time. A linear scan that only tracks a current index and target, however, uses O(1) auxiliary space. Both are linear-time operations but they have different memory bounds; the output representation and whether it counts as auxiliary memory must be stated.

Copies, views and accumulators

Creating new int[values.Length] allocates a second n-element array, then copies the input. The new array remains live at the end, so it contributes Θ(n) additional storage (whether it is called output or auxiliary space must be stated). The copy operation itself also reads and writes Θ(n) elements.

A streaming sum is a different tradeoff: it reads all elements but retains only a fixed-width accumulator, using Θ(1) auxiliary memory. A recursive linked-list traversal may keep Θ(n) call frames, whereas an iterative traversal can keep a single current pointer. If an algorithm stores every processed value in a growing list, the memory requirement becomes Θ(n) even if it originally seemed to use only one loop counter.

C#

C# | Linear.cs

int[] copy = new int[values.Length];
Array.Copy(values, copy, values.Length);

C++

C++ | linear.cpp

#include <vector>

std::vector<int> copy = values; // O(n) copied element storage

Analysis: The copied array requires O(n) auxiliary space; the copy also takes O(n) time.

The stated bound describes stored elements and active call frames. Actual byte counts also depend on runtime, allocator and element representation.

Linear does not always mean inefficient

When every input item must influence the answer, Θ(n) may be asymptotically optimal. Finding a maximum in an unsorted array requires inspecting all candidates in the worst case, and producing n output elements requires at least Ω(n) output work. A hash index might speed up repeated queries, but constructing or maintaining that index has its own time and memory cost.

A linear scan is often preferable for short collections, sequential storage or infrequent lookups because it is simple, cache-friendly and requires almost no setup. When comparing algorithms, distinguish one query from a sequence of many queries and include any preprocessing cost. The right implementation depends on the overall workload rather than the class name alone.

Practical example: validating player records

Suppose a server needs to inspect every connected player’s score to find the maximum. Without a maintained index or summary, any uninspected player could have the largest value, so a full pass is necessary in the worst case. The algorithm uses Θ(n) time but only Θ(1) extra memory for the current best score and player reference. If you also build a sorted leaderboard, that is a separate operation whose complexity must be analyzed independently.

Batch processing, streaming and sequential file reading often benefit from this predictable behavior. A linear pass can be easier to test and safer to maintain than a complicated index, especially when the collection is small or updated constantly. An index becomes attractive when many queries reuse the same data.

Common mistake

Watch out: A single loop is not automatically O(n): the work inside the loop matters. Appending to a collection, running another scan for each item, or comparing strings whose lengths grow can change the total complexity.

Try it yourself

Write two versions of a search: one that exits as soon as it finds the target, and one that counts every match. Compare their best and worst cases.

1. Define exactly what n represents.
2. Count the key operation in the best and worst case where relevant.
3. Count the maximum simultaneously live memory.
4. Check your prediction in the Big O explorer.

Continue learning

Big O overview · Time complexity · Space complexity · Compare classes