Time Complexity: Array creation methods
O(n)
0
0
Array creation methods in Ruby - Time & Space Complexity
Understanding Time Complexity
When we create arrays in Ruby, the time it takes can change depending on how we do it.
We want to know how the time grows as the array gets bigger.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
arr = Array.new(n) { |i| i * 2 }
This code creates an array of size n, filling each element with twice its index.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Filling each element of the array by running the block once per element.
- How many times: Exactly
ntimes, once for each element.
How Execution Grows With Input
As the array size n grows, the number of times the block runs grows the same way.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 |
| 100 | 100 |
| 1000 | 1000 |
Pattern observation: The operations increase directly with the size of the array.
Final Time Complexity
Time Complexity: O(n)
This means the time to create the array grows in a straight line with the number of elements.
Common Mistake
[X] Wrong: "Creating an array with a block is instant and does not depend on size."
[OK] Correct: Each element is set by running the block, so the time grows with the number of elements.
Interview Connect
Understanding how array creation time grows helps you write efficient code and explain your choices clearly in interviews.
Self-Check
"What if we create an array by repeating the same value instead of using a block? How would the time complexity change?"