224 views

Consider the problem of sorting $n$ single digit integers (base $10$). This problem can be solved in time

1. $O(n \log n)$ but not $O(n \log \log n)$
2. $O(n \log \log n)$ but not $O(n)$
3. $O(n)$ but not $O(n / \log \log n)$
4. $O(n / \log \log n)$
5. None of the above.

It is given in the question we have input as $n$ single digit base $10$ integers .

It has two cases ,

case 1:-

if $n \leq10$ then we have n distinct digit which can be sort trivially in constant amount of time .

So for case 1 it will take O(1) amount time .

Case 2:-

If $n >10$ then , it means we have repeated digits which can take values from $[0,9]$ .

So this can be done easily by traversing the array once and counting how many times each integers occurs from the given n integers.

The program looks like:- The complexity of the program is $\theta(n)$ .

So correct answer is (C) .

the above mentioned procedure is called counting sort

Also bro how can we guarantee that we cant do in O(n / ( log ( log n ) ) )

is it because for comparison based sorting we cant do better than O(nlogn) time

@jiren we are not using comparison based sorting here so that $\theta(n logn)$ logic won't apply here .

we can't do it in $\frac{n}{loglogn}$ because we have to traverse the whole array atleast once to examine all the elements which took atleast $O(n)$ time.

@Kabir5454 browhat i wanted to convey is that there are basically two types of sorting techniques that we learn in GATE syllabus

1. Linear time sorting ( Counting sort )

2. Comparison based sorting ( All sorting techniques we learn except radix sort )

since linear lime sorting is O(n) time and we used it so remaining option is comparison based sorting which takes O(nlogn) time minimum

now

what i wanted to ask is how can we guarantee that there is no Sorting algorithm whose time complexity is n/loglogn

I currently don't have any proof for it but by intuition to sort an array we need to examine all the elements once with examining all the elements once we can't sort them . To examine all the elements we need atleast O(n) time . So by this we can conclude we need atleast O(n) amount time not less than that.

@Kabir5454 You are correct here. We have to go through the array atleast once which itself will take O(n) T.C. and make a frequency array of the 10 integers.

@jiren It can't be done in lesser time for sure.