Time Complexity: For loop with ranges
O(n)
0
0
For loop with ranges in Kotlin - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time it takes to run a for loop with ranges changes as the range size grows.
How does the number of steps grow when the range gets bigger?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
for (i in 1..n) {
println(i)
}
This code prints numbers from 1 up to n using a for loop with a range.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: The loop runs once for each number from 1 to n.
- How many times: Exactly n times, where n is the size of the range.
How Execution Grows With Input
As n grows, the number of times the loop runs grows the same way.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 |
| 100 | 100 |
| 1000 | 1000 |
Pattern observation: The number of operations grows directly with n. If n doubles, the work doubles.
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 range.
Common Mistake
[X] Wrong: "The loop runs in constant time because it just prints numbers."
[OK] Correct: Each print takes time, and since the loop runs n times, the total time grows with n.
Interview Connect
Understanding how loops grow with input size helps you explain code efficiency clearly and confidently in interviews.
Self-Check
"What if we changed the loop to run from 1 to n squared (1..n*n)? How would the time complexity change?"