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
Radix sort Big O
Heap sort Big O
No comments:
Post a Comment