Array Operations Time Complexity | Java Fresher Interview
Fast recall
Quick revision
Core answer
ArrayList does) is amortized O(1) but O(n) on the resize copy.Whether you know which array operations are cheap (index access) versus expensive (insert/delete/search) and why
Assuming insertion or search in an array is O(1) like index access, or confusing array with ArrayList growth
Tie O(1) access to contiguous memory + base-address arithmetic, and explain ArrayList's amortized O(1) resize
Interview-ready guide
Interview answer
The key thing about arrays is that the cost depends entirely on which operation you mean.
Accessing or updating an element by its index is O of one, constant time, and the reason is that arrays live in contiguous memory. The address of element i is just the base address plus i times the element size, so the CPU computes that in one step and jumps straight there. Where freshers slip is assuming everything is that fast.
Searching for a value, if the array isn't sorted, is O of n, because in the worst case you scan every element. Inserting or deleting in the middle is also O of n, because once you make or remove a slot, every element after it has to shift over by one position. The end case is special: adding to the end of an ArrayList is amortized O of one.
It's usually constant, but every so often the backing array fills up, and the ArrayList allocates a bigger array, often double the size, and copies everything over, which is O of n for that one operation. Because doubling makes those resizes rare, the average cost per add stays constant. One distinction I'd draw is between a plain Java array and an ArrayList.
A plain array is fixed-size; you can't grow it. The growth behavior, the resize and copy, is something ArrayList does on top of an array. So in interviews I'm careful to say index access is O of one, but search and middle insertion are O of n, and only a sorted array unlocks O of log n binary search.
Array Operations Time Complexity | Java Fresher Interview
Direct Answer
A Java array gives O(1) access by index and O(1) update, because elements sit in contiguous memory and the address is computed arithmetically. But search is O(n) (scan), and insert/delete in the middle is O(n) because everything after the spot must shift. Arrays are fixed-size; growing one (as ArrayList does) is amortized O(1) but O(n) on the resize copy.
Code Example
int[] a = {10, 20, 30, 40, 50};
int x = a[3]; // O(1): jump to base + 3*4 bytes -> 40
a[3] = 99; // O(1): direct write
// O(n) search: may touch every element
int idx = -1;
for (int i = 0; i < a.length; i++) if (a[i] == 99) { idx = i; break; }
// O(n) middle insert with ArrayList: elements after index 1 shift right
var list = new java.util.ArrayList<>(java.util.List.of(1, 2, 3, 4));
list.add(1, 99); // {1, 99, 2, 3, 4} - shifted 2,3,4
Common Mistakes & Pitfalls
- 'Insertion is O(1)': only at the end of an
ArrayList(amortized); middle insertion is O(n) due to shifting. - 'Search is fast': unsorted search is O(n); only a sorted array enables O(log n) binary search.
- Array vs ArrayList: plain arrays are fixed-size; resizing is something
ArrayListdoes, not arrays themselves. - Ignoring the resize cost:
ArrayList.addis amortized O(1), but a single resize copies all n elements.
Check your understanding
Answer these without looking back at the article.
- What is the difference between an array and an ArrayList?
- How does ArrayList resize internally?
- When would you prefer a linked list over an array?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.