Time Complexity: One-dimensional arrays
O(n)
0
0
One-dimensional arrays in Java - Time & Space Complexity
Understanding Time Complexity
When working with one-dimensional arrays, it is important to understand how the time to process them grows as the array gets bigger.
We want to know how the number of steps changes when the array size increases.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
int sumArray(int[] arr) {
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
}
return sum;
}
This code adds up all the numbers in a one-dimensional array and returns the total.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: The for-loop that visits each element in the array once.
- How many times: Exactly once for each element in the array, so as many times as the array length.
How Execution Grows With Input
As the array gets bigger, the number of steps grows in a straight line with the size.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 additions |
| 100 | 100 additions |
| 1000 | 1000 additions |
Pattern observation: Doubling the array size doubles the work needed.
Final Time Complexity
Time Complexity: O(n)
This means the time to sum the array grows directly with the number of elements.
Common Mistake
[X] Wrong: "Since the loop is simple, the time is constant no matter the array size."
[OK] Correct: Even a simple loop must run once per element, so more elements mean more steps.
Interview Connect
Understanding how loops over arrays scale is a key skill that helps you reason about many coding problems clearly and confidently.
Self-Check
"What if we changed the loop to run only half the array? How would the time complexity change?"