I'm learning more about algorithms and data structures.
According to Wikipedia and other reliable sources, an insertion sort has a worst-case time complexity of O(n2). I'm attempting to measure that complexity in code:
def swap(n, i, j): first, second = n[i], n[j] n[i] = second n[j] = first def insertion_sort(n): size, steps = len(n), 0 for i in range(1, len(n)): j = i steps += 1 while j > 0 and n[j - 1] > n[j]: swap(n, j - 1, j) steps += 1 j = j - 1 return size, steps print "size: %d, steps: %d" % insertion_sort([i for i in xrange(1000-1, -1, -1)])
Above is Python, a simple swap method for swapping values at given indices, and a simple insertion sort algorithm which also holds a count of how many iterations/operations have been performed.
The final line creates an array which looks like
[999, 998, ... 0], 1000 items in the worst possible sorting order: reverse.
When I execute this code, I see that for the array of length 1000, I've taken 500499 steps to sort it properly.
Obviously I'm doing something wrong here. Why am I not seeing 10002 (100000) iterations being required, if this is the expected worst-case behavior?