-1
$\begingroup$

Given are $n$ integer numbers in the range $0$ to $5n$.

A SubSort algorithm organizes the numbers into $k=n/100$ sets, $s_{1}$, …, $s_{k}$ , each containing $100$ numbers, such that the following conditions hold:

i. In each set, $𝑠_{𝑖}$, the 100 numbers are not necessarily sorted.

ii. All numbers in set $𝑠_{𝑖}$ are smaller than all numbers in $𝑠_{𝑗}$, if and only if $𝑖 < 𝑗$.

Can the worst case time complexity of SubSort algorithm be $O(n)$?

This is my solution for the problem:

We can insert all elements into an array A, and as all elements are integers in the range of $[0,5n]$ we can use CountingSort to sort the array. This will cost us $O(n)$ time in the worst case.

Now we can create $k$ new arrays $s_{i},...,s_{k}$ and copy the first 100 elements into array $s_{i}$ and for every i<j≀k we copy all elements from $A[(j*100)-((j-1)*100)+1]$ to $A[j*100]$ to $s_{j}$. This will cost us an additional $O(n)$ time in the worst case.

In total we have $O(n)+O(n)∈O(n)$ time complexity in the worst case.

The official solution is below:

We can sort all numbers and then split them into sets of 100 (each set will be sorted as well, although not requested). The sorting of all the elements will be linear since all numbers are integers in the range 0 to 𝑛 5 , and we can use radix sort in the following manner: Each number k is represented using base n by 6 integer keys, π‘Žπ‘– , 0 ≀ 𝑖 ≀ 5. That is a key k = π‘Ž0 + π‘Ž1𝑛 + π‘Ž2𝑛 2+ . . π‘Ž5𝑛 5 . Then we can sort the set of keys using counting sort.

I don't quiet understand what they did with the change of base and how it helps them and I wondered if maybe someone can shed some light on why their solution works, and if mine does.

$\endgroup$
3
  • $\begingroup$ Are you sure that the upper bound on the value of the input elements is $5n$ and not $n^5$? $\endgroup$
    – Steven
    Jul 31, 2021 at 15:12
  • $\begingroup$ We require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing $\endgroup$
    – D.W.
    Jul 31, 2021 at 16:22
  • $\begingroup$ @D.W. This is an exam question written by my professor, I'm sure she won't mind.. :) $\endgroup$ Aug 1, 2021 at 5:20

1 Answer 1

1
$\begingroup$

Assuming the upper bound on the maximum value of the $n$ input elements is $5n$ (as written in the question) then your solution works. Their solution works too but it is overcomplicated.

If the maximum value of the $n$ input elements is at most $n^5$, then your solution would require time $\Omega(n^5)$.

In general, if all $n$ input element are written in base $k$ (where $k$ fits in a [constant number of] memory word[s]) and are between $0$ and $k^m -1$, Radix sort takes at most $m$ iterations, each of which requires $O(n)$ time.

They chose $k=n$, so that $m \le 6$ (since $n^m - 1 \le n^5$ is equivalent to $m \le \log_n (1+ n^5)$ and $\log_n (1+ n^5) \le 1 + \log_n n^5 = 1+5$). The overall time spent is then $O(m \cdot n) = O(n)$.

$\endgroup$
0

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.