Basic Array Operations Time Complexity
The next table shows the time complexity of basic operations for arrays.
| Operation | Best Case Time Complexity | Worst Case Time Complexity | Average Case Time Complexity |
|---|---|---|---|
| Insert | O(1) | O(n) | O(n) |
| Delete | O(1) | O(n) | O(n) |
| Search | O(1) | O(n) | O(n) |
Search operation
As we discussed previously and as it can be seen from the above, the main advantage of the array is that we can access an arbitrary item in constant time if we know the index of that item in an array. But if we don't know what item we are looking for, the lookup operation takes O(N) time complexity as we must provide a Linear Search for an element.
Delete operation
If we want to delete an item by index, we can do it in constant time.
However, because arrays are represented with continuous memory blocks, removing an arbitrary item (except for the last item) means we have to deal with "holes" in a data structure. The next picture illustrates it.
To get rid of holes, we have to shift all the items from the "hole" to the end of the array, one position closer to the beginning of the array. And in the worst case, if we remove the first item, we have to shift all the other items, and the time complexity of this operation will be O(N). In the best case, we will have O(1) time complexity when removing the last item.
Insert operation
Like deleting elements, when inserting an item into an array, we may need to shift existing elements to make space for the new item. In the worst-case scenario, when inserting at the beginning of the array, we would need to shift the entire array, resulting in a time complexity of O(n). However, when inserting at the end of the array, we can simply place the new item without any shifting, resulting in a time complexity of O(1).
Все було зрозуміло?
Зміст курсу
Algorithms and Data Structures Overview
Algorithms and Data Structures Overview
Basic Array Operations Time Complexity
The next table shows the time complexity of basic operations for arrays.
| Operation | Best Case Time Complexity | Worst Case Time Complexity | Average Case Time Complexity |
|---|---|---|---|
| Insert | O(1) | O(n) | O(n) |
| Delete | O(1) | O(n) | O(n) |
| Search | O(1) | O(n) | O(n) |
Search operation
As we discussed previously and as it can be seen from the above, the main advantage of the array is that we can access an arbitrary item in constant time if we know the index of that item in an array. But if we don't know what item we are looking for, the lookup operation takes O(N) time complexity as we must provide a Linear Search for an element.
Delete operation
If we want to delete an item by index, we can do it in constant time.
However, because arrays are represented with continuous memory blocks, removing an arbitrary item (except for the last item) means we have to deal with "holes" in a data structure. The next picture illustrates it.
To get rid of holes, we have to shift all the items from the "hole" to the end of the array, one position closer to the beginning of the array. And in the worst case, if we remove the first item, we have to shift all the other items, and the time complexity of this operation will be O(N). In the best case, we will have O(1) time complexity when removing the last item.
Insert operation
Like deleting elements, when inserting an item into an array, we may need to shift existing elements to make space for the new item. In the worst-case scenario, when inserting at the beginning of the array, we would need to shift the entire array, resulting in a time complexity of O(n). However, when inserting at the end of the array, we can simply place the new item without any shifting, resulting in a time complexity of O(1).
Все було зрозуміло?
