# Sorting algorithms run time

## Homework Statement

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?

thanks

## The Attempt at a Solution

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

Code:
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

Related Engineering and Comp Sci Homework Help News on Phys.org
mgb_phys
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

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
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 :)

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.

Example:
Code:
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

while(i<N): # done N times
l[i] = l[o] # N times