Time Complexity: For loop with step and downTo
O(n)
0
0
For loop with step and downTo in Kotlin - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time it takes to run a for loop with a step and downTo changes as the input size grows.
Specifically, how many times does the loop run when counting down with steps?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
for (i in 100 downTo 1 step 2) {
println(i)
}
This code counts down from 100 to 1, skipping every other number, and prints each value.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: The for loop that runs from 100 down to 1, stepping by 2.
- How many times: It runs about half as many times as the numbers between 100 and 1, because it skips every second number.
How Execution Grows With Input
As the starting number grows, the loop runs fewer times than the total numbers because of the step of 2.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 5 |
| 100 | 50 |
| 1000 | 500 |
Pattern observation: The number of operations grows roughly half as fast as the input size because of the step of 2.
Final Time Complexity
Time Complexity: O(n)
This means the time to run the loop grows in a straight line with the size of the input, even with stepping down.
Common Mistake
[X] Wrong: "Because the loop steps by 2, the time complexity is constant or much smaller than linear."
[OK] Correct: Even though the loop skips numbers, the number of steps still grows proportionally with input size, so it is still linear.
Interview Connect
Understanding how loops with steps and counting down affect time helps you explain how your code scales clearly and confidently.
Self-Check
"What if we changed the step from 2 to 3? How would the time complexity change?"