I have array of 10 elements. Integer[] arr = new Integer10; What is the time complexity when I add 5th element like arr[5]=999;. I strongly believe that time complexity in arrays for insertion is O(1) , but on some literatures its said that for insertion on arrays (not arraylist) T.C is O(N) because the shifting occurs. How there can be shifting occured? It is not dynamic array.
Here the sources which I believe they are wrong:
O(1) accurately describes inserting at the end of the array. However, if you're inserting into the middle of an array, you have to shift all the elements after that element, so the complexity for insertion in that case is O(n) for arrays. End appending also discounts the case where you'd have to resize an array if it's full.
Inserting and deleting elements take linear time depending on the implementation. If we want to insert an element at a specific index, we need to skip all elements from that index to the right by one position. This takes linear time O(N).
3.https://www.log2base2.com/data-structures/array/insert-element-particular-index-array.html
If we want to insert an element to index 0, then we need to shift all the elements to right.
For example, if we have 5 elements in the array and need to insert an element in arr[0], we need to shift all those 5 elements one position to the right.
CodePudding user response：
There's a misunderstanding:
arr[5]=999; is a direct assignment, not an 'insertion' where shifting would occur, so yes: it's O(1)
Insertion on the other hand consists of the following steps:
- if array is full, create a new array
-
- and copy data below index (<) to 0
- copy data equal and above index (>=) to
index 1 - assign value
arr[index]=newValue;
So insertion, because it has to copy/move n-index elements on each insert, is considered O(n), because big-oh notation is designed to showcase worst-case.
Now, with MXX registers and parallel piplines on GPUs and stuff like that, we can speed this up by another big (constant) factor, but the problem itself remains in the O(n) category.
CodePudding user response：
Not to argue with other answers, but I think the OP ask about direct assignment on array arr[5]=999; This operation will assign the value 999 to 5th index in array (if array has length 6 or more). It will not do any shifting or allocation. and for this operation the notion is definitely is O(1)
CodePudding user response：
There are two use cases of inserting data in the array.
- Inplace replacement
- Shift the data
In first case (Inplace replacement), we generally have code like arr[5] = 99. For this use case, we are not going to shift the data of index 5 to index 6 and so on. Hence, the time complexity of such operation is O(1).
Whereas, in second case (Shift data), for inserting data at index 5, we will first shift the data of index 5 to index 6, and index 6 data to index 7 and so on. In this case, the time complexity of such operation would be O(N)