Time Complexity of Array Operations

When working with arrays, it is essential to understand the time complexity of common operations. This helps in writing efficient code, especially when dealing with large datasets. Time complexity represents how the runtime of an operation grows as the size of the array (N) increases.

Summary Table

Operation	Best Case	Average Case	Worst Case
Insertion (by index)	O(1)	O(N)	O(N)
Deletion (by index)	O(N)	O(N)	O(N)
Traversal	O(N)	O(N)	O(N)
Update (by index)	O(1)	O(1)	O(1)
Search (Linear)	O(1)	O(N)	O(N)
Search (Binary - Sorted)	O(1)	O(log N)	O(log N)

1. Insertion

Insertion adds a new element to the array. The time complexity depends on where the new element is inserted.

• Best Case – O(1): Inserting at the end (append) in a dynamic array takes constant time because no other elements need to be moved.
• Average Case – O(N): When inserting at a random position in the array, half the elements on average need to be shifted one step to the right. That is, in an array of size N, approximately N/2 elements are moved. While N/2 is technically less than N, asymptotic notation drops constants, so O(N/2) is still written as O(N).
• Worst Case – O(N): Inserting at the very beginning requires shifting all N existing elements to the right to make space for the new element, resulting in O(N) time.

2. Deletion

Deleting an element involves removing it and shifting subsequent elements to fill the gap. This is true for static and dynamic arrays.

• Best Case – O(N): Even when deleting the last element (which requires no shifting), array implementations in many environments don’t make an exception, so it's still considered O(N) in general analysis for safety.
• Average Case – O(N): Deleting a random element in an array of size N usually requires shifting N/2 elements to the left. Like insertion, this leads to O(N/2) → O(N) after removing the constant.
• Worst Case – O(N): Deleting the first element is most expensive — it requires all N-1 elements to be shifted left by one index.

3. Traversal

Traversal means visiting every element of the array, often using a loop. Regardless of data values or order, the number of steps required is equal to the number of elements.

• Best Case – O(N): Even if you’re checking something simple like printing values, you must touch every element once.
• Average Case – O(N): On average, the loop runs from start to end, processing each element.
• Worst Case – O(N): There’s no shortcut — each element needs to be accessed at least once.

4. Update

Updating an element means replacing the value at a known index. Since arrays support direct indexing, this operation is done in constant time.

• Best Case – O(1): Any index update (like arr[0] = 99) takes the same amount of time.
• Average Case – O(1): Whether updating the first, middle, or last element, it’s always a single step.
• Worst Case – O(1): No matter how big the array, one update step equals one memory write.

5. Search (Linear)

Linear search scans each element one-by-one from left to right until the target is found or the array ends.

• Best Case – O(1): If the element is found at index 0, only one comparison is needed.
• Average Case – O(N): On average, the desired element lies in the middle, so N/2 elements are checked. This simplifies to O(N) in asymptotic terms.
• Worst Case – O(N): If the element is not present or is at the last index, all N elements must be compared.

6. Search (Binary, Sorted Array)

Binary search only works on sorted arrays. It repeatedly halves the search space by comparing the middle element, achieving logarithmic performance.

• Best Case – O(1): If the target is exactly the middle element of the array, it is found in just one step.
• Average Case – O(log N): Each comparison reduces the search space by half. On average, the number of comparisons is proportional to log₂N.
• Worst Case – O(log N): The worst case occurs when the element is at either end or not present. Even then, only log₂N comparisons are made before concluding the result.

Note: Binary search requires the array to be sorted beforehand. If sorting is needed, that cost (usually O(N log N)) must be considered separately.