There is no summary available of the big O notation for operations on the most common data structures including arrays, linked lists, hash tables etc.
6 Answers
Information on this topic is now available on Wikipedia at: Search data structure
+----------------------+----------+------------+----------+--------------+
| | Insert | Delete | Search | Space Usage |
+----------------------+----------+------------+----------+--------------+
| Unsorted array | O(1) | O(1) | O(n) | O(n) |
| Value-indexed array | O(1) | O(1) | O(1) | O(n) |
| Sorted array | O(n) | O(n) | O(log n) | O(n) |
| Unsorted linked list | O(1)* | O(1)* | O(n) | O(n) |
| Sorted linked list | O(n)* | O(1)* | O(n) | O(n) |
| Balanced binary tree | O(log n) | O(log n) | O(log n) | O(n) |
| Heap | O(log n) | O(log n)** | O(n) | O(n) |
| Hash table | O(1) | O(1) | O(1) | O(n) |
+----------------------+----------+------------+----------+--------------+
* The cost to add or delete an element into a known location in the list
(i.e. if you have an iterator to the location) is O(1). If you don't
know the location, then you need to traverse the list to the location
of deletion/insertion, which takes O(n) time.
** The deletion cost is O(log n) for the minimum or maximum, O(n) for an
arbitrary element.
-
2There is some confusion in deletion in array. Some say , 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. And also some say, no need to fill the blank space, it can be filled by the last element. Sep 25, 2016 at 18:13
-
1Also, what if we want to insert an element in an array at a first position ? Would that not cause the entire array to be shifted? So shouldnt O(n) be the insertion time for an array ? Sep 25, 2016 at 18:22
-
2Note that you need to distinguish between an unsorted and a sorted array. Shifting/filling the elements of the array is only a concern of a sorted array, therefore the linear complexity instead of
O(1)
on an unsorted array. Regarding your thoughts about finding the element you want to delete, you again have to distinguish between finding an element and deleting it. The complexity for deletion assumes that you already know the element you're going to delete, that's why you haveO(n)
on a sorted array (requires shifting) andO(1)
on an unsorted array. Sep 25, 2016 at 19:06 -
I guess I will start you off with the time complexity of a linked list:
Indexing---->O(n)
Inserting / Deleting at end---->O(1) or O(n)
Inserting / Deleting in middle--->O(1) with iterator O(n) with out
The time complexity for the Inserting at the end depends if you have the location of the last node, if you do, it would be O(1) other wise you will have to search through the linked list and the time complexity would jump to O(n).
-
The complexity of inserting into the middle of a singularly linked list is O(n). If the list is doubly-linked and you know the node you want to insert at it is O(1) Sep 23, 2008 at 18:42
-
I had forgot about to add the iterator part. Thanks for pointing it out Sep 24, 2008 at 0:32
-
2@Rob: it may a silly doubt, but i am not able to understand how can you insert in the doubly linkedlist in O(1)? if i have
1 <-> 2 <-> 3 <-> 4
and if i have to insert 5 between 3 and 4, and all i have is pointer to the head node (i.e. 1) i have to traverse in O(n). am i missing something?– BhushanSep 3, 2011 at 16:17 -
The time complexity to insert into a doubly linked list is O(1) if you know the index you need to insert at. If you do not, you have to iterate over all elements until you find the one you want. Doubly linked lists have all the benefits of arrays and lists: They can be added to in O(1) and removed from in O(1), providing you know the index. If the index to insert/remove at is unknown, O(n) is required. Note that finding an element always takes O(n) if your list is unsorted (log(n) otherwise) Jul 28, 2014 at 17:39
-
1@FuriousFolder : Even if it knows the index eg say position 5, how does the pointer still reach there in constant time in order to do the insert/delete operation? I am still having trouble understanding this concept.– PosiedonSep 11, 2016 at 16:25
Keep in mind that unless you're writing your own data structure (e.g. linked list in C), it can depend dramatically on the implementation of data structures in your language/framework of choice. As an example, take a look at the benchmarks of Apple's CFArray over at Ridiculous Fish. In this case, the data type, a CFArray from Apple's CoreFoundation framework, actually changes data structures depending on how many objects are actually in the array - changing from linear time to constant time at around 30,000 objects.
This is actually one of the beautiful things about object-oriented programming - you don't need to know how it works, just that it works, and the 'how it works' can change depending on requirements.
Amortized Big-O for hashtables:
- Insert - O(1)
- Retrieve - O(1)
- Delete - O(1)
Note that there is a constant factor for the hashing algorithm, and the amortization means that actual measured performance may vary dramatically.
-
What is Big-O of inserting N items into hash set? Think twice. Sep 24, 2008 at 22:09
-
Amortized, it's N. You may have issues with resizing the backing array, though. Also, it depends on your method for handling conflicts. If you do chaining and your chaining insertion algorithm is N (like at the tail of a singly-linked list), it can devolve into N^2.– Hank GaySep 25, 2008 at 8:33
-
1This is wrong. You have the wrong definition of "amortized". Amortized means the total time for doing a bunch of operations divided by the number of operations. The worst-case performance for inserting N items is definitely O(N^2), not O(N). So the operations above are still O(n) worst-case, amortized or not. You are confusing it with the "average" time complexity assuming a certain distribution of hash functions, which is O(1).– newacctMay 26, 2009 at 3:46
-
1They still tell people that hashtables are O(1) for insertion/retrieval/delete even though a hashtables that resizes itself is most certainly NOT going to have constant performance on the insert that triggers a resize. I've always heard that explained as amortization. What do you call it?– Hank GayMay 26, 2009 at 9:34