Time Complexity Analysis of Single Loops
Learn how to calculate the Big O time complexity of a single loop and understand how it scales with input size.
Big O and the Single Loop
Whenever you write a loop in a technical interview, the very first question the interviewer will ask is, "What is the time complexity?" Analyzing a single loop is the foundational step in mastering Big O notation.
O(N) - Linear Time
The most common loop scenario is iterating through every element of an array.
for (int i = 0; i < n; i++) {
print(i);
}
If n is 10, the loop runs 10 times. If n is 1,000, it runs 1,000 times. The execution time grows directly in proportion to n. This is O(n), or Linear Time.
O(1) - Constant Time
What if a loop is hardcoded to always run a specific number of times, regardless of the input size?
for (int i = 0; i < 5; i++) {
print(n);
}
Even if n is a billion, the loop only runs 5 times. Because the execution time does not scale with n, this is O(1), or Constant Time.
O(log N) - Logarithmic Time
What if the update step multiplies the counter instead of adding to it?
for (int i = 1; i < n; i *= 2) {
print(i);
}
If n is 16, i becomes 1, 2, 4, 8, 16. The loop only runs 5 times. The number of operations grows logarithmically as the search space halves (or doubles). This is O(log n).
The Takeaway
To analyze a single loop, look at three things: where it starts, the condition where it ends (in relation to n), and how the counter is updated. This will tell you if your algorithm is linear, logarithmic, or constant.
If the loop iterates from 0 to N incrementing by 1, the time complexity is strictly O(N) Linear Time.
No. Big O measures the worst-case scenario. Even if you break early in the best case, the worst case still requires checking all N elements, so it remains O(N).
O(N) + O(N) = O(2N). However, in Big O notation, we drop constants, so the final time complexity is still O(N).
It halves the number of operations (N/2), but because we drop constants in Big O, it is still considered O(N) linear time.
Because the variable grows exponentially, it reaches N in far fewer steps. Mathematically, it takes log2(N) steps, hence O(log N).