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.

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).

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.

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.