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

Homework Help: Sorting algorithms run time

  1. Dec 11, 2009 #1
    1. The problem statement, all variables and given/known data

    hi, I was asked to notice a pattern involving the run times of sorting algorithms.. however, the run time timer program I have keeps giving me different values for the same length lists :| will the pattern/formula be an approximation then? also, I read that the run time should follow n^2 or some kind of quadratic relation.. I just can't see it, the runtime values I'm getting are no way quadratic. could anybody help me?


    2. Relevant equations

    3. The attempt at a solution

    here is my selection sort code , it is written in python:

    Code (Text):

    def swapper(L, i):
        larger = i
        for e in range(i+1 , len(L)):
            if L[e] > L[larger]:
                larger = e
        return larger    

    def non_ascending(L):
        i = 0
        while i != len(L)-1:
            larger = swapper(L,i)
            L[i], L[larger] = L[larger], L[i]
            i += 1
  2. jcsd
  3. Dec 11, 2009 #2


    User Avatar
    Science Advisor
    Homework Helper

    It's difficult to test because of things like caches.
    You either need to do the run 100s of times an take an average
    or you should analyse the algorithm to decide the big-O
  4. Dec 11, 2009 #3
    ah, thanks for the speedy reply. I was certain that something was off with my testing method. could you show me how (briefly at least?) I could analyze my algorithm to decide the big-O?

    thanks a lot :)
  5. Dec 13, 2009 #4

    That's its bigO run time, which you get by taking the worst case time of your algorithm. The worst case time is when you have N (N>1) values, how long will it take to sort? This is figured out by counting your operations and adding them/multiplying them together.

    Code (Text):

    while(i<N): #done N times
      k[i] = k[o] #assigned N times
    the O(n) = n^2 because n assignemnts in n loops = n(n)=n*2

    if your code is
    Code (Text):

    while(i<N): # done N times
      k[i] = k[o] #N times
      l[i] = l[o] # N times
    the O(n) = n^2 because n+n assignments in n loops = n(2n)=2n*2, but 2 (as are all constants) is negligible so O(n) = n^2
    Last edited: Dec 14, 2009
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook