5

I was reading about big O notation in java programming. I found the following table it shows different big O for different data structures.

enter image description here

http://bigocheatsheet.com/

My questions are:

  1. If I want to delete an item in an array, is it O(n^2)? (search and delete)
  2. If I want to delete an item in a stack, is it O(n)?
  3. Which one is more effective, is it a single linked list or double single list?
  4. In what case is that the insert operation is O(1) or O(n) in a hash table?
  5. If I want to delete an item in a binary search tree, is it O(log(n)*log(n)) while insert is just O(log(n))?

Thanks.

skrtbhtngr
  • 2,223
  • 23
  • 29
Joe
  • 109
  • 1
  • 8
  • These all questions are simple to understand if the data structure are understood clearly. Concepts like how data is inserted, deleted and searched. – Saurav Sahu Nov 21 '16 at 12:07

3 Answers3

5
  1. If you want to delete an item from an array, first you have to search it (takes O(n)) and then you have to shift the items to fill the gap (takes O(n)). So, the effective time complexity is O(n).
  2. If you want to delete an item from a stack, you can only delete the topmost element (a property of the stack data structure). So, it can be done in O(1).
  3. Which type of linked list is more effective depends on your requirements. For instance, if you want to save memory, then you might not use doubly-linked lists due to the overhead of maintaining an extra pointer reference. But, if you want to be able to traverse your list in both directions, you have to use a doubly-linked list. Implementation of a doubly-linked list is a bit lengthy as you have to perform more pointer operations, but, many operations (like deleting the last element) can be performed with ease.
  4. We prefer to use Hash tables because we can achieve O(1) insertion and search time. O(n) insertion time is taken by almost all other data structures. (O(n) class includes O(log n), O(1), etc.). Suppose we use separate chaining in the hash table where each chain is a sorted linked list. Then, for each insertion, we need to search the linked list to find the right position to insert (just like Insertion Sort), which will take O(n) worst-case time.
  5. If you have to delete an element from a BST, first you have to search it (takes O(log n) in average case) and then you have to replace the deleted node with its inorder successor or predecessor (takes O(log n)). So, the effective average-case deletion time is O(log n).
skrtbhtngr
  • 2,223
  • 23
  • 29
  • If I want to delete an item in a queue, is it O(n)? (search and delete) .. thanks – Joe Nov 21 '16 at 10:56
  • 1
    @Joe: Stack allows deletion of ONLY the topmost element. So, you don't have to search for it. Since we know that the topmost element is to be deleted, we can simply remove it. Delete operation is called Pop and Insert operation is called Push in stacks. Example: http://stackoverflow.com/a/3825329/1866196 – skrtbhtngr Nov 21 '16 at 10:59
  • #4 doesn't answer the corresponding question – Nicolas Filotto Nov 21 '16 at 11:05
  • @ skrtbhtngr I asked about the queue not stack... thanks you – Joe Nov 21 '16 at 11:11
  • 1
    Oh, right! Even in a queue, you can delete from only one end, called Front. So, we do not need to search and no need to shift elements. So, deletion from a queue (dequeue operation) also takes O(1) time. – skrtbhtngr Nov 21 '16 at 11:13
  • @ skrtbhtngr Hi ,, what is runtime for add in a queue if it is implemented by an array? my answer is O(n) .. Is it correct? thanks – Joe Nov 21 '16 at 12:00
  • If by add you mean insertion, then for an array implementation of a queue, the complexity will still be O(1). Same time is for deletion operation. – skrtbhtngr Nov 21 '16 at 12:04
3

Let me answer your questions:

  1. Nope. It's O(n) + O(n) = O(n).
  2. Nope, it's O(1) but you only have access to one, very on top element. For other elements it's O(n).
  3. Double single list will be not worse, might be faster sometimes, but needs more memory for additional references.
  4. Best time - when there is no element with that hash yet, Worst when all inserted elements have the same hash according to some modulo. For example, if you compare modulo 3 of hashes and your hashing function always returns a number which is 3k for some k, you'll have O(n).
  5. Nope, according to your table, it's worst case O(n).

I'll explain more in a minute.

xenteros
  • 15,586
  • 12
  • 56
  • 91
  • Hi ,, what is runtime for add in a queue if it is implemented by an array? my answer is O(n) .. Is it correct? thanks – Joe Nov 21 '16 at 11:59
  • The insert time would be O(n) but u should use a list with two pointers : to first and last element. – xenteros Nov 21 '16 at 12:15
2
  1. When you do one operation and then the other, you don't multiply their complexity - the max one wins. In this case O(n) + O(n) = O(n)
  2. Does stack have a 'delete arbitrary item' API? If you expose the underlying data structure that's a different thing, but a stack usually has a single way to "pop" elements
  3. What's the use case?
  4. Look up what happens during hash collisions.
orip
  • 73,323
  • 21
  • 116
  • 148