Question

Show that any array of integers $\mathit{x}\left[1\dots n\right]$ can be sorted in O (n + M) time, where

role="math" localid="1659938331794" $\mathit{M}\mathbf{=}\begin{array}{c}\mathbf{m}\mathbf{a}\mathbf{x}{\mathbf{x}}_{\mathbf{i}}\mathbf{-}\mathbf{m}\mathbf{i}\mathbf{n}{\mathbf{x}}_{\mathbf{i}}\\ \mathbf{i}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{i}\end{array}$

For small M, this is linear time: why doesn’t the $\mathit{\Omega }\left(nlogn\right)$ lower bound apply in this case?

Short answer

The $\Omega \left(n\log n\right)$ lower bound does not apply because this is not a comparison-based sort, and also because the information beforehand about the range of the elements in the array is given.

Step-by-step solution

Explain Array

There are different kind of Array. 1’s, 2’s, 3^rd dimensional and multi-dimensional array’s. In the above question there will be sorted array technique through we can combine single sorted array in k/n elements. To check that see below detail related to combine theory of array.

Show that any array of integers x[1…n] can be sorted in  O (n + M)  time

Consider the any array of integers x [1...n] can be sorted in O (n + M) time where,

$\mathit{M}\mathbf{=}\begin{array}{c}{\mathbf{maxx}}_{\mathbf{i}}\mathbf{-}{\mathbf{minx}}_{\mathbf{i}}\\ \mathbf{i}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{i}\end{array}$

Counting sorting takes O(n) times to find maxX_i and minX_i , and then the size can be established as,

$\begin{array}{rcl}S& =& \max \left(x_i\right)-\min \left(x_i\right)+1\\ & =& M+1\\ & & \end{array}$

The array for counting is $C\left[\min \left(x_i\right),\dots ,\max \left(x_i\right)\right]$. Travers the array x [1...n] and for each occurrence of x [i] , the corresponding $C\left[x\left[i\right]\right]$ is incremented by 1. If C [i] is greater than zero, then the element i is the output of the array. The total time complexity is $O\left(n+S\right)=O\left(n+M\right)$.

Since counting sort is not based on comparison, it is not subject to lower bound $\Omega \left(n\log n\right)$limit.

Therefore,The $\Omega \left(n\log n\right)$lower bound does not apply because this is not a comparison-based sort, and also because the information beforehand about the range of the elements in the array is given.