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?
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.
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.
All the methods shared are linear time complexity, that is O(n). But directly/in-directly they are traversing same element in array twice and Aquarius (The Asker) is looking for one-time traversing approach. Following code traverse the array once and sort it while traversing.
int left = 0, right = arr.length - 1;
while (left < right)
{
while (arr[left] == 0 && left < right)
left++;
while (arr[right] == 1 && left < right)
right--;
if (left < right)
{
arr[left] = 0;
arr[right] = 1;
left++;
right--;
}
}
For the record,
O(c*n) = O(n), where c is a constant
In the solution, array is traversed twice. So, the order is O(2n) = O(n). Big-O notations ignore the constants. n and 2n both grows linearly with the value of n. Multiplying or adding a constant to a function doesn't change the behavior of a function.
"Linear time" means that the time the algorithm requires increases linearly with the size of the array. Here, for every item you add to the array, you have two more comparisons (i.e., 2n).
O(2n), O(1221n), O(n), O(n/2). All of these are linear. It means the time of execution always changes constantly. So if you have array of size 10 for example, it will always take twice more time than sort an array with size 5.
