Time Complexity

Time complexity describes how the running time of an algorithm grows as the input size grows. It does not try to predict exact seconds. It describes the shape of growth.

This matters because two correct programs can behave very differently on large inputs.

Core Idea

Time complexity counts the dominant amount of work an algorithm performs. A loop over n elements is usually linear. A nested loop over all pairs of elements is usually quadratic. A search that repeatedly halves the remaining range is usually logarithmic.

The goal is to compare algorithms in a machine-independent way. Exact timing depends on hardware, language, interpreter, operating system, and data. Growth rate is more durable.

The analysis usually starts by identifying the operation that repeats. That operation may be a comparison, a loop iteration, a dictionary lookup, a recursive call, or an edge relaxation. Once the repeated work is visible, count how the number of repetitions grows.

Time complexity often describes a case:

• Best case: the most favorable valid input.
• Worst case: the least favorable valid input.
• Average case: expected behavior under some input distribution.

Beginner algorithm analysis usually focuses on worst case because it gives a dependable upper bound.

Example Contracts

has_duplicate(values) accepts a sequence of values and returns whether any value appears more than once. Its nested-loop version compares pairs directly, so the input-size variable is n = len(values).

has_pair_sum(values, target) accepts numbers and a target sum. It returns whether two different positions add to target. The brute-force version checks every pair, so the number of candidate pairs is the real cost driver.

Python Example

def has_duplicate(values):
    seen = set()
 
    for value in values:
        if value in seen:
            return True
        seen.add(value)
 
    return False

This function does one pass over values. If hash set operations are treated as constant time on average, the time complexity is O(n).

The loop runs at most once per input value. Even if the duplicate appears early, the worst case is that no duplicate exists and every value must be checked.

Counting Work

Consider a direct pair check:

def has_pair_sum(values, target):
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            if values[i] + values[j] == target:
                return True
    return False

The outer loop chooses the first index. The inner loop chooses a later second index. The number of pairs grows roughly like n * n / 2, so the time complexity is O(n^2).

The exact number of loop iterations is less important than the growth pattern. Doubling n makes the number of possible pairs about four times larger.

Reading Constraints

Time complexity becomes practical when connected to input limits.

If n is at most 100, an O(n^2) solution may be fine. If n is 200,000, an O(n^2) solution is usually impossible. The same algorithm idea can be acceptable or unacceptable depending on the input size.

Common Confusions

Time complexity is not the same as wall-clock speed. A theoretically worse algorithm can be faster on tiny inputs because it has smaller constant overhead.

Time complexity also depends on the case being described. Best case, average case, and worst case may be different. A search may find the target immediately in the best case and scan everything in the worst case.

Another common mistake is ignoring hidden work inside operations. In Python, x in some_list is linear in the list length, while x in some_set is average constant time. A one-line expression can still hide a loop.

When To Use It

Use time complexity when deciding whether a solution can handle the expected input size. If n can be 100, a quadratic loop may be fine. If n can be 200,000, a quadratic loop is usually not practical.

Use it also when comparing two correct solutions. A simpler solution can be better for small inputs. A more complex solution is justified when it changes the growth enough to meet the constraints.

The Main Point

Time complexity describes growth, not stopwatch time. A useful estimate names the input-size variable and counts the operation pattern that grows with it.