Time Complexities

Searching

Name of Searching Algorithm	Time Complexity	What the elements mean
Linear Search	O(n)	n = Number of elements
Binary Search	O(log n)	n = Number of elements
Jump Search	O(sqrt n)	n = Number of elements Calculate Jump size as sqrt(n)

Sorting

Name of Sorting Algorithm	Time Complexity	What the elements mean
Bubble Sort	O(n^2)	n = Number of elements
Selection Sort	O(n^2)	n = Number of elements
Insertion Sort	O(n^2)	n = Number of elements
Merge Sort	O(n*log(n))	n = Number of elements
Heap Sort	O(n*log(n))	n = Number of elements
Count Sort	O(n+k)	n = Number of elements and k = Length of the range of the input elements
Quick Sort	O(n*log(n))	n = Number of elements
Radix Sort	O(nd)	n = Number of elements and d = Number of digits in the largest element

Traversal

Name of Traversal	Time Complexity
Inorder Traversal	O(n)
Preorder Traversal	O(n)
Postorder Traversal	O(n)
Breadth First Search	O(V+E) V = Number of Vertex, E = Number of Edge
Depth First Search	O(V+E) V = Number of Vertex, E = Number of Edge

Trees

Name of Tree	Time Complexity	What the elements mean
AVL	Everything is O(logn)	n = Number of nodes
Red Black Tree	Everything is O(logn)	n = Number of nodes
Binary Search Tree	Insertion = O(h)Deletion = O(log n)	h = Height of BST n = Number of nodes

Heap

Name	Time Complexity	What the elements mean
Heapify	O(logn)	n = Number of element in the heap