Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Loop running time

  1. Apr 26, 2013 #1
    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. jcsd
  3. Apr 26, 2013 #2

    mfb

    User Avatar
    2016 Award

    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.
     
  4. Apr 26, 2013 #3
    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)?
     
  5. Apr 27, 2013 #4

    rcgldr

    User Avatar
    Homework Helper

    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.
     
  6. Apr 27, 2013 #5

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  7. Apr 27, 2013 #6
    So this is a comparison based sort, right?
     
  8. Apr 27, 2013 #7

    mfb

    User Avatar
    2016 Award

    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
     
  9. Apr 27, 2013 #8
    That does not work with duplicates.
     
  10. Apr 27, 2013 #9

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper



    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.
     
  11. Apr 27, 2013 #10

    mfb

    User Avatar
    2016 Award

    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.
     
  12. Apr 27, 2013 #11

    rcgldr

    User Avatar
    Homework Helper

    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
  13. Apr 28, 2013 #12

    rcgldr

    User Avatar
    Homework Helper

    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Loop running time
Loading...