Array Data Structure with Time and Space Complexity.
For further actions, you may consider blocking this person and/or reporting abuse
For further actions, you may consider blocking this person and/or reporting abuse
Trix Cyrus -
Bhargav Ditani -
Menard Maranan -
Nikola Perišić -
Top comments (3)
Array implementations may provide O(1) insertion and deletion at the end of the array. E.g. Javascript arrays.
Thank you for your comment! You are correct that insertion and deletion at the end of arrays usually have a time complexity of O(1).
Why Insertion and Deletion Operations are O(n)?
Insertion: When you insert a new item at the beginning of the array, it is placed at the first index. However, all the remaining elements in the array must be shifted one position back. For example, if the array is [1, 2, 3] and you want to add 0, the array will become [0, 1, 2, 3]. This operation requires shifting all elements, which takes O(n) time.
Deletion: Similarly, if you want to delete the first element of the array, the first item is removed, and all remaining items must be shifted one position forward. This operation also takes O(n) time.
Feel free to use this explanation to clarify how insertion and deletion at the beginning of an array have a complexity of O(n).
One of my favourite questions to ask developers is to:
implement a queue of arbitrary length, with O(1) lookahead, insertion and removal.
describe the memory use of your solution and offer ways to ensure too much memory isn't being used. How does your change affect the O of insertion and removal (worst case, average case, best case).
If you could apply a length restriction to the maximum length of the queue, how would this alter your solution to 1 and 2, and how would the new big O be affected?