3,137 views

Which of the following algorithms sort $n$ integers, having the range $0$ to $(n^2 -1)$, in ascending order in $O(n)$ time?

1. Selection sort
2. Bubble sort
4. Insertion sort

### 1 comment

Only Radix sort among options can sort in linear time i.e O(n)  rest are comparison sorts

so ans is C

ans c except radix sort all given algorithms take O(n^2) time so ans is radix sort it performs sorting digit by digits taking O(n) time
by

Radix sort take O(N) time .

how??? can u  explain..
Radix sort run loop = Max no. of digits in one Number and Number of digit is constant [can't be n].

so loop run n times only.
Selection sort takes O(n2) time.
Bubble sort takes O(n2) time.
Insertion sort takes O(n2) time.

So, option (C) is correct.