How to sort binary array in linear time? [duplicate]

Question

http://www.techiedelight.com/sort-binary-array-linear-time/

Linear time means that we have to traverse the array only one time but according to the solution here, we will first traverse the array to find the number of zeros, and then we traverse it again to fill the first part of the array with zeros and the remaining part with ones.

So, how is that linear time solution? What point am I missing?

Answer 1

The time complexity linear time is expressed as O(n). The means that the running time increases linearly with respect to the size of input. An example of this summing all the elements of an array, proportional to the length of the array.

Specifically to your example, have a look at this loop in Sort():

int zeros = 0;
for (int i = 0; i < n; i++)
    if (A[i] == 0)
        zeros++;

This loop traverses linearly through A[], and sums the amount of zeroes. Linear time is also applied in these loops:

int k = 0;
while (zeros--)
    A[k++] = 0;

// fill all remaining elements by 1
while (k < n)
    A[k++] = 1;

As you are simply traversing A[] once.

These operations combined are O(2n), since the array is traversed twice. Therefore the function Sort() is a O(2 * n) operation, which is equivalent to O(n).

Here is another example. If you had to sort 100 binary numbers in comparison to 10 binary numbers, which would take more time? In this case, sorting 100 binary numbers would be 10 times longer than sorting 10 binary numbers. This is because linear time increases linearly with respect to size of input n.

Answer 2

An algorithm is said to take linear time, or O(n) time, if its time complexity is O(n). Informally, this means that for large enough input sizes the running time increases linearly with the size of the input.

As this alogorithm transverses the array twice. It is still linear. Think of a linear equation y = 2*x.