Loop Running Time: O(n) Not O(n2)

[zorro]

Can someone explain why the running time of following piece of pseudo code is O(n) and not O(n²)?

for i := 0 to n - 1
while A[A] != A
swap(A, A[A])
end while
end for

The for loop executes at most n times and the inner while loop executes at most n-1 times, giving a worst case time of O(n²)

 

[mfb]

This follows from the algorithm: it "sorts" A. The while condition is satisfied at most O(n) times. Take some simple example (like n=5), and check how it works.

 

[zorro]

I tried the output for 1 3 4 2 0 and found that the While loop executes 4 times only for i=0, it doesn't execute for other i's. The output was sorted. This of course took O(n) time.
Isn't the worst case complexity of comparison based sorting algorithms O(nlogn)?

 

[rcgldr]

Isn't the worst case complexity of comparison based sorting algorithms O(nlogn)?

This isn't a comparason based sort. The worst case requires (n-1) swaps. The simplest pattern to produce the worst case pattern is to rotate the numbers left 1 place, for example if there are 8 numbers, one of the worst case patterns is 1 2 3 4 5 6 7 0.

 

[AlephZero]

Isn't the worst case complexity of comparison based sorting algorithms O(nlogn)?

This is a special case, because it only sorts the numbers 0, 1, ... (n-1).

If the array A contained arbitrary numbers (say n = 3 and A[0] = 1000, A[1] = -2000, A[2] = 42) the algorithm does not work at all. But a general comparison based sort like Quicksort or Heapsort would work, of course.

 

[zorro]

This is a special case, because it only sorts the numbers 0, 1, ... (n-1).

If the array A contained arbitrary numbers (say n = 3 and A[0] = 1000, A[1] = -2000, A[2] = 42) the algorithm does not work at all. But a general comparison based sort like Quicksort or Heapsort would work, of course.

So this is a comparison based sort, right?

 

[mfb]

It sorts special A (permutations) only. And this can be done quicker:

for i := 0 to n - 1
  A[i] = i
end for

 

[zorro]

That does not work with duplicates.

 

[AlephZero]

It sorts special A (permutations) only. And this can be done quicker:

To be fair, the "swap" operation could maintain the order of other data related to the permutation, but your ultra-fast version doesn't do that.

Each "swap" operation puts at least one element of the array into the correct place, and the algorithm never does a "swap" that moves an element out of its correct place. So the total number of "swaps" is always <= n.

 

[mfb]

That does not work with duplicates.

Hmm, right.

Anyway, it is a very special sorting algorithm, which allows it to be quicker than n log n. You can know the final position of elements in constant time.

 

[rcgldr]

This "index" sort method could be used after a conventional sort that sorted an array of indexes to an array of structures, to swap the array of structures in place to sort them according to the array of sorted indexes.

Each "swap" operation puts at least one element of the array into the correct place.

Some examples:

7 6 5 4 0 3 2 1
1 6 5 4 0 3 2 7
6 1 5 4 0 3 2 7
2 1 5 4 0 3 6 7
5 1 2 4 0 3 6 7
3 1 2 4 0 5 6 7
4 1 2 3 0 5 6 7
0 1 2 3 4 5 6 7

2 0 1 5 3 4 7 6
1 0 2 5 3 4 7 6
0 1 2 5 3 4 7 6
0 1 2 4 3 5 7 6
0 1 2 3 4 5 7 6
0 1 2 3 4 5 6 7

 

[rcgldr]

This "index" sort method could be used after a conventional sort that sorted an array of indexes to an array of structures, to swap the array of structures in place to sort them according to the array of sorted indexes.

Example pseudo-code for this:

//      generate indexes

    for(i = 0; i < n; i++)
        I[i] = i;

//      sort indexes based on A[]

    sort(I, ...);

//      swap data based on sorted indexes

    for(i = 0; i < n; i++){
        while(     I[i] !=  I[I[i]] ){
            swap(A[I[i]], A[I[I[i]]]);
            swap(  I[i],    I[I[i]] );
        }
    }

Example of how this works. Using the values swapped during the "swap sort" of the sorted indexes as indexes to swap A will duplicate the permutation process needed to sort A. I also did this with B, the original sorted indexes to show that this algorithm duplicates the permutation that produced the sorted indexes.

A 7 6 5 4 0 3 2 1   (array   original)
B 0 1 2 3 4 5 6 7   (indexes original)
I 4 7 6 5 3 2 1 0   (indexes sorted)

A 7 6 5 0 4 3 2 1   (swapped A[I[0] = 4] with A[I[I[0]] = 3])
B 0 1 2 4 3 5 6 7   (swapped B[I[0] = 4] with B[I[I[0]] = 3])
I 3 7 6 5 4 2 1 0   (swapped   I[0] = 4  with   I[I[0]] = 3 )

A 7 6 5 3 4 0 2 1   (swapped A[I[0] = 3] with A[I[I[0]] = 5])
B 0 1 2 5 3 4 6 7   (swapped B[I[0] = 3] with B[I[I[0]] = 5])
I 5 7 6 3 4 2 1 0   (swapped   I[0] = 3  with   I[I[0]] = 5 )

A 7 6 0 3 4 5 2 1   (swapped A[I[0] = 5] with A[I[I[0]] = 2])
B 0 1 4 5 3 2 6 7   (swapped B[I[0] = 5] with B[I[I[0]] = 2])
I 2 7 6 3 4 5 1 0   (swapped   I[0] = 5  with   I[I[0]] = 2 )

A 7 6 2 3 4 5 0 1   (swapped A[I[0] = 2] with A[I[I[0]] = 6])
B 0 1 6 5 3 2 4 7   (swapped B[I[0] = 2] with B[I[I[0]] = 6])
I 6 7 2 3 4 5 1 0   (swapped   I[0] = 2  with   I[I[0]] = 6 )

A 7 0 2 3 4 5 6 1   (swapped A[I[0] = 6] with A[I[I[0]] = 1])
B 0 4 6 5 3 2 1 7   (swapped B[I[0] = 6] with B[I[I[0]] = 1])
I 1 7 2 3 4 5 6 0   (swapped   I[0] = 6  with   I[I[0]] = 1 )

A 7 1 2 3 4 5 6 0   (swapped A[I[0] = 1] with A[I[I[0]] = 7])
B 0 7 6 5 3 2 1 4   (swapped B[I[0] = 1] with B[I[I[0]] = 7])
I 7 1 2 3 4 5 6 0   (swapped   I[0] = 1  with   I[I[0]] = 7 )

A 0 1 2 3 4 5 6 7   (swapped A[I[0] = 7] with A[I[I[0]] = 0]) A = sorted
B 4 7 6 5 3 2 1 0   (swapped B[I[0] = 7] with B[I[I[0]] = 0]) B = indexes sorted
I 0 1 2 3 4 5 6 7   (swapped   I[0] = 7  with   I[I[0]] = 0 ) I = sorted