# Loop running time

1. Apr 26, 2013

### zorro

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

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(n2)

2. Apr 26, 2013

### Staff: Mentor

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.

3. Apr 26, 2013

### 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)?

4. Apr 27, 2013

### rcgldr

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.

5. Apr 27, 2013

### AlephZero

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.

6. Apr 27, 2013

### zorro

So this is a comparison based sort, right?

7. Apr 27, 2013

### Staff: Mentor

It sorts special A (permutations) only. And this can be done quicker:
Code (Text):
for i := 0 to n - 1
A[i] = i
end for

8. Apr 27, 2013

### zorro

That does not work with duplicates.

9. Apr 27, 2013

### AlephZero

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.

10. Apr 27, 2013

### Staff: Mentor

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.

11. Apr 27, 2013

### 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.

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

Last edited: Apr 27, 2013
12. Apr 28, 2013

### rcgldr

Example pseudo-code for this:

Code (Text):

//      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.

Code (Text):

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

Last edited: Apr 28, 2013