The Gateway to Computer Science Excellence

+2 votes

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,492 answers

195,439 comments

100,704 users