I need to write an algorithm which will sort an array $A[1..n]$ with $\sqrt n$ distinct elements in $\Theta(n)$ time and $\Theta(\sqrt n)$ space?

The solution must use hash-tables and advanced data structures including any variation of trees is not allowed.

I thought of the following:

1 Sort(A, n)
2   init B[2][sqrt(n)] //B[1][sqrt(n)] will hold the distinct elements
                       //B[2][sqrt(n)] will hold the number of occurrences
                       //of element B[1][k] in the original array A
3   for i<-0 to n
4       hash(A[i]) //the hash function will also update B[2][i] counter
                   //of occurrences of A[i] in A
5   Quick-Sort(B[1][sqrt(n)]) //quick-sort will also move
                                  //B[2][k] when B[1][k] is moved
                                  //so that they're aligned
6   count<-0    //keeps track of the next location in A
7   for i<-0 to sqrt(n)
8       for j<-0 to B[2][i]
9           A[count]<-B[1][i] //copy the sorted array into the original array
10          count++ 

In terms of space complexity it looks right to me since we're using $\sqrt n$ additional space for the hash table.

In terms of time complexity I'm running into problems. The quick-sort operation (or according to my understanding any optimal sort for that matter) on line 5 takes $\Theta(\sqrt n \log{\sqrt n})=o(n)$ which is not $\Theta(n)$.

How can I modify the sorting part/algorithm in order to arrive to $\Theta(n)$ complexity?

  • $\begingroup$ I just realized that if the time complexities of other loops in the algorithm are $\Theta(n)$ and the sort is $o(n)$ then it's still $\Theta(n)$ in total. Am I right? $\endgroup$ – Yos Jun 7 '17 at 19:06
  • 1
    $\begingroup$ If you have an $o(n)$ algorithm and want to make it a $\Theta(n)$ algorithm, just add a loop running in time $\Theta(n)$. That said, any sorting algorithm runs in $\Omega(n)$, and indeed your algorithm already runs in time $\Theta(n)$. Moreover, it is pretty stupid to ask you to given an algorithm which performs at least as bad as $\Omega(n)$. Usually we are looking for fast algorithms rather than for slow ones. $\endgroup$ – Yuval Filmus Jun 7 '17 at 19:13
  • $\begingroup$ Under must you mean it is given as task condition? $\endgroup$ – rus9384 Jun 7 '17 at 19:46
  • $\begingroup$ Yes it was given $\endgroup$ – Yos Jun 7 '17 at 19:47
  • $\begingroup$ @YuvalFilmus should I delete the post? I feel like I realized that the algorithm satisfies the conditions already as you mentioned $\endgroup$ – Yos Jun 7 '17 at 19:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.