To learn how to calculate time complexity, describe how an algorithm’s work grows as the input size grows. Define the input, identify a basic operation, count how often it runs, and simplify the resulting expression only after establishing that count. This process produces Big O notation, the standard way to describe runtime complexity.

Time complexity analysis focuses on growth rather than the exact time on one machine. Constants, hardware differences, and small implementation details matter less than whether the work grows linearly, quadratically, logarithmically, or exponentially.

How to Calculate Time Complexity from Input Size and a Basic Operation

Start by naming the input size. Use n for the number of items in an array, the length of a string, or the number of nodes in a structure. Then choose a basic operation, such as a comparison, assignment, arithmetic operation, or array access. Count how many times that operation executes.

For one loop that examines every item, the count is proportional to n:

for each item in an array: compare the item with a target

The comparison runs n times, so the complexity is O(n). If the loop performs three constant-time operations per item, the count might be 3n, but Big O removes the constant and still gives O(n).

Do not infer complexity from the number of statements alone. A statement inside a loop may execute millions of times, while several statements outside the loop may execute only once. Count execution frequency instead.

How Do Sequential and Nested Loops Affect Runtime Complexity?

Sequential sections add their costs. If one loop takes O(n) and a later loop takes O(n), the total is O(n + n), which simplifies to O(n). More generally, add the expressions first, then remove constants and lower-order terms. O(n² + n) becomes O(n²) because the quadratic term dominates as n grows.

Nested loops usually multiply their costs. If an outer loop runs n times and an inner loop also runs n times for every outer iteration, the operation runs n × n times. The result is O(n²).

Different bounds change the product. An outer loop that runs n times with an inner loop that runs 10 times has cost 10n, or O(n). An inner loop that runs from 1 through the current outer index performs 1 + 2 + … + n operations, which equals n(n + 1)/2 and simplifies to O(n²).

When loop bounds depend on separate inputs, retain both variables. For example, comparing every item in an array of size n with every item in an array of size m costs O(nm), not automatically O(n²).

When Does a Loop Become Logarithmic?

A loop is logarithmic when each iteration reduces the remaining work by a constant factor. A counter that doubles, such as 1, 2, 4, 8, and so on, reaches n after about log₂(n) iterations. A counter that halves follows the same growth pattern:

while n is greater than 1: divide n by 2

Its complexity is O(log n). The logarithm’s base is omitted in Big O because changing the base only changes a constant factor.

A loop that increases its counter by one is different: 1, 2, 3, …, n requires O(n) iterations. If a logarithmic loop is placed inside a linear loop, multiply the costs to get O(n log n).

How Does Time Complexity Analysis Handle Recursion and Cases?

For recursion, write a recurrence that describes the work in one call and the smaller calls it creates. A recursive linear search that checks one item and then searches the remaining items has the worst-case recurrence:

T(n) = T(n − 1) + O(1)

Each call removes one item and adds constant work, so the calls total O(n). The base case stops when no items remain. By contrast, a recurrence such as T(n) = T(n/2) + O(1) has O(log n) complexity because the input is halved at every call.

State the case being analyzed when the algorithm can stop early. For a linear search, the best case is O(1) when the first item matches. The average case is O(n) when a match is equally likely at any position, because the expected scan covers about half the input. The worst case is O(n) when the match is last or absent. These cases differ because the input’s position or contents change how much work the algorithm performs.