Advanced Database Management System - Tutorials and Notes: Time complexity of sorting algorithms

Search Engine

Please visit, subscribe and share 10 Minutes Lectures in Computer Science

Time complexity of sorting algorithms / Big O notation / Asymptotic notation / Bubble, Insertion, Radix, Selection, Heap sort time complexities

Time complexity

Time complexity is one of the measures to calculate the performance of an algorithm or program.
The time needed by an algorithm expressed as a function of the size of a problem is called the Time Complexity of the algorithm. The time complexity of a program is the amount of computer time it needs to run to completion.
For any algorithm, it can be calculated as Best case, Average case and Worst case. Among these the Big-oh (Big O) notation is the most widely used notation for comparing functions.
The following table shows us some of the well known algorithms time complexity;

 Algorithm Time complexity Best case Average case Worst case Bubble sort O(n) O(n2) O(n2) Insertion sort O(n) O(n2) O(n2) Selection sort O(n2) O(n2) O(n2) Quick sort O(n log (n)) O(n log (n)) O(n2) Merge sort O(n log (n)) O(n log (n)) O(n log (n)) Radix sort O(nk) O(nk) O(nk) Heap sort O(n log (n)) O(n log (n)) O(n log (n))

***********

Time complexity of sorting algorithms
Time complexity of algorithms
Big O notation time complexity
Insertion sort Big O
Selection sort Big O
Heap sort Big O