Algorithmic Complexity and Data Structures

Algorithmic complexity describes how an algorithm’s required work or storage grows with input size. A data structure organizes values so particular operations are possible or efficient. Choosing the right representation can change the amount of work the program needs to do, not just the speed of one instruction. 1

Search a sorted list without checking every item

Suppose a catalog contains sorted integer identifiers. A linear search inspects entries until it finds the target or reaches the end. A binary search inspects the middle and uses the ordering to discard half the remaining candidates.

Count array positions inspected, not milliseconds. That makes the difference visible without depending on which machine runs the example.

public sealed record SearchResult(bool Found, int Probes);

public static class Search
{
    public static SearchResult Linear(int[] values, int target)
    {
        int probes = 0;
        foreach (int value in values)
        {
            probes++;
            if (value == target) return new SearchResult(true, probes);
        }
        return new SearchResult(false, probes);
    }

    public static SearchResult Binary(int[] sorted, int target)
    {
        int low = 0, high = sorted.Length - 1, probes = 0;
        while (low <= high)
        {
            int middle = low + (high - low) / 2;
            int value = sorted[middle];
            probes++;
            if (value == target) return new SearchResult(true, probes);
            if (value < target) low = middle + 1;
            else high = middle - 1;
        }
        return new SearchResult(false, probes);
    }
}

int[] ids = Enumerable.Range(0, 128).ToArray();
Console.WriteLine(Search.Linear(ids, 999).Probes); // 128
Console.WriteLine(Search.Binary(ids, 999).Probes); // 8

def linear(values, target):
    probes = 0
    for value in values:
        probes += 1
        if value == target:
            return True, probes
    return False, probes


def binary(sorted_values, target):
    low = 0
    high = len(sorted_values) - 1
    probes = 0
    while low <= high:
        middle = low + (high - low) // 2
        value = sorted_values[middle]
        probes += 1
        if value == target:
            return True, probes
        if value < target:
            low = middle + 1
        else:
            high = middle - 1
    return False, probes

ids = list(range(128))
print(linear(ids, 999)[1])  # 128
print(binary(ids, 999)[1])  # 8

Put names on the growth

A worst-case linear search inspects a number of positions proportional to the number of entries, conventionally described as O(n). Binary search over a sorted array requires O(log n) probes: doubling the number of candidates adds roughly one halving step. Here n is the input length, not the numeric magnitude of an identifier. 1

Big-O is an asymptotic upper-bound notation. It does not state an exact duration, and saying an operation is O(n) should be accompanied by what case and resource are being discussed. Our counter measures inspections; a real runtime also pays for comparisons, branches, memory access, and function overhead.

Include the cost of obtaining the representation

If the data is unsorted and only one search is needed, sorting it first may cost more than simply scanning it. Repeated queries can justify maintaining a sorted array or a different index. A hash-based set is another option when membership matters but sorted order does not; its memory use and behavior under collisions are separate trade-offs.

Do not select a structure from one operation alone. Consider insertion, deletion, ordered traversal, duplicate handling, and the actual sizes involved. A simpler algorithm can win on tiny inputs even with worse asymptotic growth.

The two implementations are teaching examples; production libraries already provide tested searches. Their purpose here is to make the reduction in work visible and to show why the required sorted representation is part of the algorithm’s promise.

Sources

1. Sedgewick and Wayne — Analysis of Algorithms, on cost models, input dependence, and growth rates.