5

Suppose there is a unsorted array A, and it contains an element x (x is the pointer of the element), and every element has a satellite variable k. So, we can get the following time complexity (for worst cases):

If we want to Search for a particular K, then it costs O(n).

if we want to Insert an element, then it costs O(1), because A just adds the element to the end.

What if we know x, then Delete it from the array A?

We have to Search for x.k first and get the index of x, then Delete x via its index in A, right?

So for Delete, it costs O(n) too, right?

thanks

Jackson Tale
  • 25,428
  • 34
  • 149
  • 271

5 Answers5

27

Finding the element with a given value is linear.

Since the array isn't sorted anyway, you can do the deletion itself in constant time. First swap the element you want to delete to the end of the array, then reduce the array size by one element.

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • 2
    That's pretty cool. You couldn't implement a general purpose delete like that though because even though the array is not sorted, it still might have some particular order to it that needs to be preserved. – dan-gph Feb 20 '12 at 09:47
  • @Dangph: That would still be sorted -- just not in ascending (or descending) order. – Jerry Coffin Feb 20 '12 at 09:56
  • 1
    @Jerry: I think authors normally distinguish between "ordered" and "sorted". A "sorted" array is specifically one in which the order depends on the values of the objects in it. An array that is ordered by insert-time is not normally described as "sorted" even when it is important that the insert-time order is preserved. – Steve Jessop Feb 20 '12 at 10:22
  • That said, the questioner calls the array "unsorted" without further comment, so I think it's fair to assume that the order is unimportant until proved otherwise. – Steve Jessop Feb 20 '12 at 10:31
  • @JerryCoffin is this how it is normally implemented? that is, to swap element in unsorted arr to end and reduce? – steviesh Nov 08 '16 at 19:11
  • @ish2f4f: In most typical cases (e.g., a C++ `vector` or a Java `ArrayList`) deleting an element in the middle of the collection can't change the order of remaining elements, so they have to move all the other elements to cover up the hole, so to speak. – Jerry Coffin Nov 08 '16 at 19:25
  • @JerryCoffin thanks, so in that case, the deletion is O(n). – steviesh Nov 08 '16 at 19:33
  • @ish2f4f: Correct. – Jerry Coffin Nov 08 '16 at 19:43
  • @JerryCoffin just to be clear, finding the element with a given index value is constant (hence arrays being random access), but finding the element of a given value is linear since you have to inspect (worst-case) every element in the array? – Yu Chen Nov 05 '17 at 22:45
  • @YuChen: Yes, searching an unsorted array normally requires a linear search. – Jerry Coffin Nov 05 '17 at 23:46
6

Yes, that's right. Also, if it's an array, deleting alone will take O(n) time because after you delete the element, you'll need to shift all the elements to the right of that element one place to the left. So, even if you know x (for example, you will only delete the first element), it will take O(n) time.

Sabbir Yousuf Sanny
  • 594
  • 4
  • 9
1

Worst case time complexity for deletion operation in a sorted array is O(n), If the array is not sorted and it is mentioned that after deletion operation order of the array shouldn't be altered then time complexity will be same as O(n) otherwise it will be O(1).

Parveen Kumar
  • 175
  • 3
  • 5
0

Unsorted Array

Ex:

Items Value     [3,   5,  1,  7,  4]
Items Address   [&1, &2, &3, &4, &5]
Deleting - Value 5

1. Deletion - Order to be preserved - O(n + n) - O(2n) ~> O(n)

i) O(n) - Finding the position of that element (Index = 1 for value 5)

ii) O(n) - After deleting that element, the rest of the items (1, 7, 4) needs to be reshuffled to hold the previous item's address. Like

Items Value     [3,   1,  7,  4]
Items Address   [&1, &2, &3, &4]

2. Deletion - Without preserving the Order - O(n + 1 + 1) - O(2 + n) ~> O(n)

i) O(n) - Finding the position of that element (Index = 1 for value 5)

ii) O(1) - Swape with the last element of the array.

Items Value     [3,   4,  1,  7,  5]
Items Address   [&1, &2, &3, &4, &5]

iii) O(1) - Delete the last element of the array.

Items Value     [3,   4,  1,  7]
Items Address   [&1, &2, &3, &4]
Vinoth Anandan
  • 1,157
  • 17
  • 15
0

Yes. It takes O(n) time to find the element you want to delete. Then in order to delete it, you must shift all elements to the right of it one space to the left. This is also O(n) so the total complexity is linear.

Also, if you're talking about statically allocated arrays, insert takes O(n) as well. You have to resize the array in order to accommodate the extra element. There are ways to amortize this running time to O(1) though.

tskuzzy
  • 35,812
  • 14
  • 73
  • 140
  • 3
    Actually, you don't have to shift anything since the array is unsorted, you can just fill the gap by using the last element. – Aurelien Ribon Sep 22 '13 at 09:56