Time Complexity: Array traversal
O(n)
0
0
Array traversal in Java - Time & Space Complexity
Understanding Time Complexity
When we look at array traversal, we want to know how the time to run the code changes as the array gets bigger.
We ask: How many steps does it take to go through all the items?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
public void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
This code goes through each item in the array and prints it out one by one.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: The for-loop that visits each element in the array.
- How many times: Exactly once for each element, 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 steps |
| 100 | 100 steps |
| 1000 | 1000 steps |
Pattern observation: Doubling the array size doubles the work done.
Final Time Complexity
Time Complexity: O(n)
This means the time to finish grows directly with the number of items in the array.
Common Mistake
[X] Wrong: "The loop runs faster because it just prints items quickly."
[OK] Correct: The speed of printing does not change how many times the loop runs; it still visits every item once.
Interview Connect
Understanding how array traversal scales helps you explain simple but important code clearly in interviews.
Self-Check
"What if we nested another loop inside to compare each element with every other? How would the time complexity change?"