19-02-2013, 10:15 AM
Insertion Sort
Insertion Sort.ppt (Size: 252 KB / Downloads: 217)
Complexity
Space/Memory
Time
Count a particular operation
Count number of steps
Asymptotic complexity
Comparison Count
Pick an instance characteristic … n, n = a.length for insertion sort
Determine count as a function of this instance characteristic.
Step Count
A step is an amount of computing that does not depend on the instance characteristic n
10 adds, 100 subtracts, 1000 multiplies
can all be counted as a single step
n adds cannot be counted as 1 step
Complexity of Insertion Sort
Time or number of operations does not exceed c.n2 on any input of size n (n suitably large).
Actually, the worst-case time is Theta(n2) and the best-case is Theta(n)
So, the worst-case time is expected to quadruple each time n is doubled