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?
j
in your while-loopO(f(n))
means resource (e.g. time, space) usage grows on the order off(n)
, rather than asf(n)
. You can think off
as being the term (scaled by unspecified factor) that eventually dominates the actual growth function, which likely has other terms. AnO(n*n)
function could actually be (e.g.)a*n*n + b*n + c*n*sqrt(n) + d*log(log(n))+e
. Also, you can have any function in theO(...)
, but (because it's used to classify algorithms) the simplest functions are used as representatives.