I came across this article regarding time complexity of dynamic arrays which clarified a lot. However I have a case based question. Say I have a dynamic array that has a total of 6 elements and suppose the 4th element is removed. In this case the deletion complexity would be O(n-index) which will be O(6-4) = 2 since the last two elements will only need to move up. Is this correct ? I have articles that give the worst case complexity saying that if the top most element is removed then time complexity would be O(n). I could not find anything that talked about removing/inserting an item from/in the center.
Add a comment
|
1 Answer
Your analysis of the number of items that need to be moved is correct. However, in big-O notation, that's still O(n). If you have n items in the list and remove something from the middle you'll have to move *0.5 * n* items. But when dealing with big-O we drop any constant multipliers so that's just O(n).
3 Comments
James Franco
I am not sure what you mean by <blockquote> If you have n items in the list and remove something from the middle you'll have to move 0.5 * n items </blockquote> How did you get 0.5 * n ?
James Franco
Ok thanks for clearing that up. How would you write time complexity for 4 element being removed from a total of 6 elements without neglecting the constant term ? Will it be
O(6 * 4/6) ? That will give me 4 which is wrong I was expecting 2
Oliver Dain
Talking about complexity for a fixed number of items doesn't make sense. Big-O is all about how the computation of time changes as a the size of the input changes.. For your question (4 being removed from an array of 6) that could mean you're always removing the last 4 items, no matter how big the array is in which case it's O(1), or it could mean you're always removing the last 2/3 of the array in which case it's O(n), or it could mean you're always removing all but the first two items (O(n)) again), etc.