Eg.
log(n!) = O(nlogn)
T(n) = T(n/2) + n
T(n) = T(n/2) + 1
T(n) = aT(n/b) + f(n)
// pseudo code
int search(A, key, n) {
int begin = 0;
int end = n - 1;
while(begin < end){
int mid = (begin + end) / 2;
if (key <= A[mid]) {
end = mid;
} else {
begin = mid + 1;
}
}
return (A[begin] == key) ? begin : -1;
}
FindPeak(A,n)
if A[n/2] is a peak then return n/2
else if A[n/2+1] > A[n/2] then
Search for peak in right half
else if A[n/2-1] > A[n/2] then
Search for peak in left half
T(n) = T(n/2) + theta(1) = O(log n)
If we need to recurse on both sides: T(n) = 2T(n/2) + O(1) = O(n)
void bubbleSort(int arr[]) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
// swap arr[j+1] and arr[j]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
void sort(int arr[]) {
int n = arr.length;
// One by one move boundary of unsorted subarray
for (int i = 0; i < n-1; i++) {
// Find the minimum element in unsorted array
int min_idx = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the first
// element
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
void sort(int arr[]) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
Split into two halves -> sort each part -> Combine
Merge two sorted halves requires O(n) Hence T(n) = 2T(n/2) + cn = O(nlogn)
void merge(int arr[], int l, int m, int r) {
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int L[] = new int[n1];
int R[] = new int[n2];
/*Copy data to temp arrays*/
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using
// merge()
void sort(int arr[], int l, int r) {
if (l < r) {
// Find the middle point
int m =l+ (r-l)/2;
// Sort first and second halves
sort(arr, l, m);
sort(arr, m + 1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
Find pivot -> Partition the array -> Sort Each half
Optimised => Random pivot Paranoid Quicksort
repeat until p > (1/x)n and < (1-1/x)n
partition (A[1...n], n, pIndex)
pivot = A[pIndex];
swap(A[1], A[pIndex]);
low = 2;
high = n + 1;
while(low < high)
while (A[low] < pivot) and (low< high) do low++;
while (A[high] > pivot) and (low < high) do high--;
if(low < high) then swap (A[low], A[high]);
swap(A[1], A[low-1]);
return low-1;
3-way Partition => Optimised Partition
| < pivot | = pivot | In Proress | > pivot |
void quicksort(A[1..n], n)
if (n == 1) return
else
Choose Pivot index // random
p = partition(A[1..n], n, pIndex)
x = quicksort(A[1..p-1], p-1)
y = quicksort(A[p+1..n], n-p)
Find the kth largest/smallest element Similar to quicksort but only need to recurse on ONE SIDE.
Select(A[1..n], n, k)
if (n == 1) then return A[1]
else Choose random pivot index pIndex
p = partition(A[1..n], n, pIndex)
if (k == p) then return A[p];
else if (k < p) then
return Select(A[1..p-1], k)
else if (k > p ) then
return Select(A[p+1], k - p)
T(n) = T(n/2) + O(n) ====> O(n)
RightRotate(node)
w = v.left
w.parent = v.parent
v.parent = w
v.left = w.right
w.right = v
LeftRotate(node)
v = w.right
v.parent = w.parent
w.parent = v
w.right = v.left
v.left = w
if curr node curr is out of balance:
if curr is left-heavy:
curr.left is balanced/ left-heavy : RightRotate(curr)
curr.left is right-heavy : LeftRotate(curr.left) RightRotate(curr)
if curr is right-heavy:
curr.right is balanced/ right-heavy : LeftRotate(curr)
curr.right is left-heavy : RightRotate(curr.right) LeftRotate(curr)
height = max(left.height + right.height) + 1Sample Code (a bit different)
// Java program for insertion in AVL Tree
class Node {
int key, height;
Node left, right;
Node(int d) {
key = d;
height = 1;
}
}
class AVLTree {
Node root;
// A utility function to get the height of the tree
int height(Node N) {
if (N == null)
return 0;
return N.height;
}
// A utility function to get maximum of two integers
int max(int a, int b) {
return (a > b) ? a : b;
}
// A utility function to right rotate subtree rooted with y
// See the diagram given above.
Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;
// Perform rotation
x.right = y;
y.left = T2;
// Update heights
y.height = max(height(y.left), height(y.right)) + 1;
x.height = max(height(x.left), height(x.right)) + 1;
// Return new root
return x;
}
// A utility function to left rotate subtree rooted with x
// See the diagram given above.
Node leftRotate(Node x) {
Node y = x.right;
Node T2 = y.left;
// Perform rotation
y.left = x;
x.right = T2;
// Update heights
x.height = max(height(x.left), height(x.right)) + 1;
y.height = max(height(y.left), height(y.right)) + 1;
// Return new root
return y;
}
// Get Balance factor of node N
int getBalance(Node N) {
if (N == null)
return 0;
return height(N.left) - height(N.right);
}
Node insert(Node node, int key) {
/* 1. Perform the normal BST insertion */
if (node == null)
return (new Node(key));
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else // Duplicate keys not allowed
return node;
/* 2. Update height of this ancestor node */
node.height = 1 + max(height(node.left),
height(node.right));
/* 3. Get the balance factor of this ancestor
node to check whether this node became
unbalanced */
int balance = getBalance(node);
// If this node becomes unbalanced, then there
// are 4 cases Left Left Case
if (balance > 1 && key < node.left.key)
return rightRotate(node);
// Right Right Case
if (balance < -1 && key > node.right.key)
return leftRotate(node);
// Left Right Case
if (balance > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
/* return the (unchanged) node pointer */
return node;
}
// A utility function to print preorder traversal
// of the tree.
// The function also prints height of every node
void preOrder(Node node) {
if (node != null) {
System.out.print(node.key + " ");
preOrder(node.left);
preOrder(node.right);
}
}
public static void main(String[] args) {
AVLTree tree = new AVLTree();
/* Constructing tree given in the above figure */
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 20);
tree.root = tree.insert(tree.root, 30);
tree.root = tree.insert(tree.root, 40);
tree.root = tree.insert(tree.root, 50);
tree.root = tree.insert(tree.root, 25);
/* The constructed AVL Tree would be
30
/ \
20 40
/ \ \
10 25 50
*/
System.out.println("Preorder traversal" +
" of constructed tree is : ");
tree.preOrder(tree.root);
}
}
// This code has been contributed by Mayank Jaiswal
successor(node)
if node.right not null then
return minNode(node.right)
parent = node.parent
child = node
while((parent not null) && (child = parent.right))
child = parent
parent = child.parent
return parent
No longer a binary tree, with max length L and n words