Array Operations
Understanding the time complexity of every operation on an array is essential for making correct data structure choices. Arrays support four fundamental op...
Insertion, Deletion, Search, and Update at Every Position
Understanding the time complexity of every operation on an array is essential for making correct data structure choices. Arrays support four fundamental operations: access, search, insertion, and deletion, each with its own complexity profile.
Access by index is the defining strength of arrays. Given a valid index i, retrieving or updating the value at position i is O(1). This constant-time random access is what makes arrays ideal for situations where you know exactly which position you need.
Search in an unsorted array requires checking each element until a match is found. In the worst case, the target is the last element or absent, requiring n comparisons. This linear search is O(n). If the array is sorted, binary search applies. Binary search works by comparing the target to the middle element; if the target is smaller, it searches the left half; if larger, the right half. Each comparison halves the search space, giving O(log n) time. Binary search requires the array to be sorted and supports only read operations, not modifications during the search.
Insertion has three distinct cases. Inserting at the end of an array with available capacity is O(1): just write the value and increment a count. Inserting at the beginning is O(n): every existing element must shift one position to the right to make room. Inserting at an arbitrary position i is O(n - i) on average, since elements from i onward must shift. In the worst case this is O(n).
Deletion mirrors insertion. Deleting the last element is O(1). Deleting the first element requires shifting all n minus one remaining elements left, costing O(n). Deleting at position i costs O(n - i) as elements shift to fill the gap.
One useful trick for deletion when order does not matter is to swap the element to delete with the last element and then reduce the count by one. This turns an O(n) deletion into an O(1) operation at the cost of changing element order.
Traversal, visiting every element once, is O(n) and is the basis of operations like sum, maximum, minimum, and printing all elements.
Worked example: rotating an array of n elements to the right by k positions. A brute force approach shifts elements one position at a time for k iterations, giving O(n times k). A clever approach reverses the whole array, then reverses the first k elements, then reverses the remaining n minus k elements. Three reversal operations each O(n) gives O(n) total, a substantial improvement.
Interview tip: for any array manipulation problem, ask whether the order of elements must be preserved. If not, swap-to-end tricks can drastically reduce deletion cost.