Algorithm Complexity

Arrays

  • Set, Check element at a particular index: O(1)
  • SearchingO(n) if array is unsorted and O(log n) if array is sorted and something like a binary search is used,
  • Similarly, Insert for arrays is basically Set as mentioned in the beginning

ArrayList:

  • AddAmortized O(1)
  • RemoveO(n)
  • ContainsO(n)
  • SizeO(1)

Linked List:

  • InsertingO(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
  • DeletingO(1), if done at the head, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
  • SearchingO(n)

Doubly-Linked List:

  • InsertingO(1), if done at the head or tail, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
  • DeletingO(1), if done at the head or tail, O(n) if anywhere else since we have to reach that position by traveseing the linkedlist linearly.
  • SearchingO(n)

Stack:

  • PushO(1)
  • PopO(1)
  • TopO(1)
  • Search (Something like lookup, as a special operation): O(n) (I guess so)

Queue/Deque/Circular Queue:

  • InsertO(1)
  • RemoveO(1)
  • SizeO(1)

Binary Search Tree:

  • Insert, delete and search: Average case: O(log n), Worst Case: O(n)

Red-Black Tree:

  • Insert, delete and search: Average case: O(log n), Worst Case: O(log n)

Heap/PriorityQueue (min/max):

  • Find Min/Find MaxO(1)
  • InsertO(log n)
  • Delete Min/Delete MaxO(log n)
  • Extract Min/Extract MaxO(log n)
  • Lookup, Delete (if at all provided): O(n), we will have to scan all the elements as they are not ordered like BST

HashMap/Hashtable/HashSet:

  • Insert/DeleteO(1) amortized
  • Re-size/hashO(n)
  • ContainsO(1)

Searching & Sorting Algorithm

Best case

Worst case

Selection sort O(N2) O(N2)
Merge sort O(N log N) O(N log N)
Linear search O(1) O(N)
Binary search O(1) O(log N)
Heapsort O(n log(n)) O(n log(n))
Bubble Sort O(n) O(n^2)
Insertion Sort O(n) O(n^2)

 

Toufiq Mahmud