Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we have explained Complexity Analysis of Dynamic Array along with Time and Space Complexity of different operations of Dynamic Array.
Table of contents:
- Introduction to Dynamic Array
- Time Complexity of Dynamic Array
- Space Complexity of Dynamic Array
Let us start with the Complexity Analysis of Dynamic Array.
Introduction to Dynamic Array
To learn about Dynamic Array in depth, go through this article.
Problem with Array is that it has fixed size. If user does not know then size of array or data beforehand then the solution is to use Linked List.
The problem with Linked list is the memory access is slow. Hence, Dynamic Array comes into picture which is a modified version of Array.
Dynamic Array is also called ArrayList in Java and Vector in C++.
In Dynamic array, the size of the array can be changed at time of execution of program. Basically, what we do in Dynamic Array is create a resize function and the size is adjusted according to input by user.
The key idea is both adding and deleting element will continue as if it is an ordinary array but when there is no space left in the array, the size of the array will be doubled and all existing elements will be copied to the new location.
With addition to resize function, all elements of previous array is copied to new array and then new element is appended. This new array is Dynamic Array.
The previous array memory is then dis-allocated / freed.
Normally, we make the size of array twice but that totally depend upon situation or what user wants.
Operations in a Dynamic Array:
- Resize Method
- Add Method (with add at a specific index)
- Delete Method (with delete at a specific index)
Time Complexity of Dynamic Array
When we increase the size of array by 1, then elements are copied from previous to new array and then new element is appended, it takes O(N).
When we double the size of array, it will take O(1) and sometimes O(N). Basically, when we increase size one by one, then all elements all copied every time, again create array, and then append. When we double the size, all elements copied only once and then appended so the average time across several insertion and deletion operation becomes O(1).
Hence, the resize operation takes O(1) in average and O(N) in the worst case.
The logic behind insert and delete operation is same as in Array data structure. The only extra step in Dynamic Array is resize which follows the following rules:
- If a new element needs to be inserted but the entire array is filled, then the size of the array is doubled using resize operation.
- If an element is deleted, we can half the size of array if possible, using the same resize operation.
Following is the summary table of Time Complexity of different operations in Dynamic Array:
| Dynamic Array operation | Worst Case | Average Case | Best Case |
|---|---|---|---|
| Resize | O(N) | O(N) | O(N) |
| Add | O(1) | O(1) | O(1) |
| Add at an index | O(N) | O(N) | O(1) |
| Delete | O(1) | O(1) | O(1) |
| Delete at an index | O(N) | O(N) | O(1) |
where:
- N = number of elements in array
- Time to read block of N elements = O(√N) not considered.
If we consider Time to read block of N elements that is O(√N), then the Time Complexity of different operations are:
| Dynamic Array operation | Worst Case | Average Case | Best Case |
|---|---|---|---|
| Resize | O(N + √N) | O(N + √N) | O(N + √N) |
| Add | O(√N) | O(√N) | O(√N) |
| Add at an index | O(N+√N) | O(N+√N) | O(√N) |
| Delete | O(√N) | O(√N) | O(√N) |
| Delete at an index | O(N+√N) | O(N+√N) | O(√N) |
Space Complexity of Dynamic Array
The space complexity of all operations in a Dynamic Array is O(1).
Specific operations like resize() increases or decreases the size of Dynamic Array but in doing so it needs no extra memory. Hence, the time complexity of resize operation is O(1) irrespective of the total size of Dynamic Array varies.
With this article at OpenGenus, you must have the complete idea of Time and Space Complexity of Dynamic Array.
