Sorting

Selection Sort ["Select" the smallest]

Find min in range [i,j] and swap with start, them move [i++]
i.e find smallest, then next smallest, and so on..
TC O(n^2) for all cases

Insertion Sort ["Insert" item to correct position]

For index [i], find its correct position i.e swap back until [i-1] item is smaller
the move [i++]
TC: O(n) for Best | O(n^2) for Avg & Worst

Bubble Sort

Compare [i] & [i+1], such that left index [i] should be smaller (i.e swap if not)
If any iteration had no swaps -> end (already sorted)
TC: O(n) for Best | O(n^2) for Avg & Worst

Merge Sort

Sort: Until [l < r] -> break down into two: [l, m] to [m+1, r]
Merge: Then using merge on [l, r]
TC: O(n logn) for all cases

Quick Sort

Choose a pivot (either [first, last, random or median] index)
Put pivot [i] in its correct position
Do same for left & right parts [D & C]
TC: O(n logn) for best & avg | O(n^2) for worst

Tips for quick sort

On first/last index -> in worst case O(n^2)

On Random Index -> worst case O(n logn)

Strings

Anagram - Word or phrase formed by rearranging the letters of a different word or phrase i.e [permutation of a string]

Lexographic Order - Order of characters as they appear in alphabet i.e [sorting a string in a,b,c,…, z (alphabetical) order]

Binary Trees

Number of Nodes

Max nodes at level l of a binary tree is 2^l. [l = 0,1,2,3,…]
Max nodes in a binary tree of height h is 2^(h+1) - 1. [h=1,2,3,…]

Balanced Binary Tree

A binary tree is considered balanced if the height difference between the left and right sub-trees of any node is[ at most 1.]
A balanced tree ensures operations like insertion, deletion, and search have O(log n) time complexity.

BST

BST Property
- Left Subtree: value(left) < value(node)
- Right Subtree: value(right) > value(node)
Height (Balanced BST)
- Best case (Balanced BST): O(log n)
- Worst case (Skewed BST): O(n)
Number of Nodes
- Minimum height for n nodes: log2(n + 1) - 1
- Maximum height for n nodes: n - 1

Heaps

Time Complexity

Insertion: O(log n)
Deletion (extract max/min): O(log n)
Build Heap: O(n)

Index Relationships (1-based)

Parent of node at index i: floor(i/2)
Left child of node at index i: 2i
Right child of node at index i: 2i + 1