Cormen Edition 3 Exercise 8.3 Question 4 (Page No. 200)

Question

Show how to sort $n$ integers in the range $0$ to $n^3-1$ in $O(n)$ time.

Comments

I think using radix sort we can solve in O(n) time

Answer 1

Assume $n$ keys sorts integers $\epsilon \left \{ 0,1,....(k-1) \right \}$

Then according to counting sort , for $k$ integers can sort $O(n)$ time.

---

Now, here is the  proof by an algorithm:

Say, $L=$ Array of $k$ empty lists for $j$ in $range\left ( n \right )$. 

$L\left [ key\left ( A\left [ j \right ] \right ) \right ],append\left ( A\left [ j \right ] \right )$

for $i$ in $range\left [ k \right ]:$

$Output.extend\left ( L\left [ i \right ] \right )$

This algorithm has time complexity $O\left ( n+k \right )$.........$(i)$

 

Now, using counting sort imagine each integer has base $b.$

Then, $digit=d=\log _{b}k+1$

Now, according to counting sort expression $(i)$ will be $O\left ( n+b \right )$

Then total time$=O\left ( \left ( n+b \right ).d \right )$

                         $=O\left ( \left ( n+b \right ).\log _{b}k \right )$

                         $=O\left ( \left ( n \right ).\log _{n}k \right )$ when $b\simeq n$

                        $=O\left ( 3n \right )=O\left ( n \right )$ [when $k=n^{3}$ a polynomial function]

Source:MIT Lecture

Comments

if range are given that  can  we apply counting short?

---

why not?

---

i have one doubt that time complexity of counting short can be more than O(n)? if we are taking

n integers in the rang 0 to 2^n?

---

Counting sort is a linear time sorting algorithm that sort in O(n+k) time when elements are in range from 1 to k.

We can’t use counting sort because counting sort will take O(n2) for range 1 to n^2-1 which is worse than comparison based sorting algorithms  Radix sort uses counting sort as a subroutine to sort.

Answer 2

counting sort will be the ans

range

is sepecified