0

We have many sorting algorithms like the mergesort which has the complexity of O(n*log(n)) in all the worst, best, average cases.
Insertion and Quicksort as well as have their own complexities in respective cases
Is there an algorithm/process in which we can have a time complexity of O(n) for the average cases?
And also what are the complexities of the System defined function of Cpp i.e. sort() and sorted in Python 3

Debi Prasad
  • 297
  • 1
  • 8

1 Answers1

0

Counting sort can give you O(N). But only under the condition that there are just a few distinct values.

pveentjer
  • 10,545
  • 3
  • 23
  • 40
  • 1
    Just to clear the ambiguity of the statement,the range of numbers should be small , countsorts complexity depends on range of the number for example if the difference between lowest and the highest integer is 10^6 then the complexity would be 10^6 – Pranshu Dubey Jul 06 '21 at 11:44