Identify Time Complexity From a Loop

1) Find the loop structure

Start by reading the loop boundaries and how the loop variable changes. The key question is: how many times does the body run as input size grows?

2) Match the growth pattern

Use the update rule to estimate the number of iterations:

• Linear growth: the variable changes by a fixed amount each time, so the loop usually runs about n times → O(n).
• Constant work: the loop does a fixed amount of work without depending on input size → O(1).
• Nested loops: multiply the work of the inner and outer loops when they are independent.
• Skipping by doubling/halving: the number of iterations grows slowly, often about log n → O(log n).

3) Simplify the final answer

Keep only the dominant term. Ignore constants and lower-order terms. For example, if your count is something like 3n + 7, the complexity is O(n).

4) Check your result

Ask whether the loop would clearly take more steps when the input size increases. If doubling the input roughly doubles the work, the answer is likely linear. If the number of steps grows by one each time the input doubles, it is likely logarithmic.