What Is The Best Case Time Complexity Of Insertion Sort Code Example


Example: what is time complexity of insertion sort

Time Complexity is:  If the inversion count is O(n),  then the time complexity of insertion sort is O(n).  Some Facts about insertion sort: 1. Simple implementation: Jon Bentley shows a three-line C version, and a five-line optimized version[1] 2. Efficient for (quite) small data sets, much like other quadratic sorting algorithms 3. More efficient in practice than most other simple quadratic (i.e., O(n2))  algorithms such as selection sort or bubble sort 4. Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each element in the input is no more than k places away from its sorted position 5. Stable; i.e., does not change the relative order of elements with equal keys 6. In-place; i.e., only requires a constant amount O(1) of additional memory space Online; i.e., can sort a list as it receives it

Comments

Popular posts from this blog

Are Regular VACUUM ANALYZE Still Recommended Under 9.1?

Can Feynman Diagrams Be Used To Represent Any Perturbation Theory?