Time Complexity: Range operators (.. and ...)
O(n)
0
0
Range operators (.. and ...) in Ruby - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time it takes to work with ranges changes as the size of the range grows.
How does using the two types of range operators affect the number of steps the program takes?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
n = 10
range_inclusive = (1..n).to_a
range_exclusive = (1...n).to_a
range_sum = 0
range_inclusive.each do |num|
range_sum += num
end
This code creates two ranges: one including the last number, one excluding it, then sums all numbers in the inclusive range.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Looping through each number in the inclusive range.
- How many times: The loop runs once for each number from 1 up to n.
How Execution Grows With Input
As the range size grows, the number of steps to sum all numbers grows at the same rate.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 steps |
| 100 | 100 steps |
| 1000 | 1000 steps |
Pattern observation: Doubling the input roughly doubles the work done.
Final Time Complexity
Time Complexity: O(n)
This means the time to complete the task grows in direct proportion to the size of the range.
Common Mistake
[X] Wrong: "Using the exclusive range operator (...) makes the loop run fewer times in a way that changes the overall time complexity."
[OK] Correct: The exclusive range just stops one number earlier, so the number of steps changes slightly but still grows linearly with input size.
Interview Connect
Understanding how range operators affect loops helps you explain how your code scales with input size, a key skill in many programming tasks.
Self-Check
"What if we used a nested loop inside the range loop? How would the time complexity change?"