Notes on Data Structures

Excellent memory refreshers on the basics of data structures: (With very cute illustrations!)

Memory refresher on time complexity:

Such complex, very wow – A guide to Algorithmic Complexity



– max-heap – all children are smaller than parent
– min-heap – all children are greater than parent
– Time complexity for insertion is O(logN)
– Heapsort => O(NlogN)

Binary Tree
– always of height logN

insertion sort => O(N2)
– Good when array size is small or almost sorted
– bubble sort
– Mergesort => O(NlogN)
– Quicksort => O(NlogN)
– Key concept: Picks an element as pivot and partitions the given array around the picked pivot
– Best case O(NlogN), average case O(NlogN), worst case O(N2)

Hash table

Count inversions

Leave a Reply