39

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 6

80

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.
4
  • 2
    There 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
  • 1
    Also, 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
  • 2
    Note 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 have O(n) on a sorted array (requires shifting) and O(1) on an unsorted array. Sep 25, 2016 at 19:06
  • That explains it. Thanks! Sep 25, 2016 at 19:58
16

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).

6
  • 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)
    – Rob Walker
    Sep 23, 2008 at 18:42
  • I had forgot about to add the iterator part. Thanks for pointing it out
    – Jose Vega
    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?
    – Bhushan
    Sep 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.
    – Posiedon
    Sep 11, 2016 at 16:25
6

Nothing as useful as this: Common Data Structure Operations:

enter image description here

4

Red-Black trees:

  • Insert - O(log n)
  • Retrieve - O(log n)
  • Delete - O(log n)
4

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.

1

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.

4
  • 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 Gay
    Sep 25, 2008 at 8:33
  • 1
    This 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).
    – newacct
    May 26, 2009 at 3:46
  • 1
    They 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 Gay
    May 26, 2009 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.