1

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?

7
  • Print out your 'sorted' list, you'll see that the algorithm is broken. You need to decrement j in your while-loop
    – tkausl
    Aug 7, 2015 at 1:26
  • Shoot, forgot that step, ack Aug 7, 2015 at 1:30
  • Updated the question to include the decrement, I'm now seeing another unexpected outcome of 500499 operations. Aug 7, 2015 at 1:32
  • 4
    You are missing the point of what big-O is. Do the test with 10 elements, 50 elements, 100 elements, 250 elements, and 500 elements. Then plot that, along with the 1000 elements on a graph. Big-O says nothing about how many iterations a particular algorithm takes.
    – user40980
    Aug 7, 2015 at 1:44
  • 2
    Very informally, O(f(n)) means resource (e.g. time, space) usage grows on the order of f(n), rather than as f(n). You can think of f as being the term (scaled by unspecified factor) that eventually dominates the actual growth function, which likely has other terms. An O(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 the O(...), but (because it's used to classify algorithms) the simplest functions are used as representatives.
    – outis
    Aug 7, 2015 at 7:32

3 Answers 3

6

Since the result of your (fixed) code still confuses you, i try to answer your question:

The O-Notation is not an exact formula notation. Only because something is O(1) doesn't mean it takes one single step, only because it is O(n²) doesn't mean it takes n² steps. The O-Notation is an abstract way to define how complex an algorithm is. Sure, you don't get your 1000² for your O(n²) with n = 1000, but that was expected. There is no O(n²/2 plus a few).

Your algorithm has to iterate over every single element and for every singe element, it needs to iterate again over a part of elements, that is essentially quadratic complexity, therefore O(n²)

See here for a list of possible (or rather, commonly used) O-notations.

1
  • 1
    "There is no O(n²/2 plus a few)" -- O(n^2/2+c) exists and is equal to O(n^2). Apr 8, 2018 at 14:28
1

O(n2) means that if you increase n from 1000 to 10000 the number of operations will be around 102=100 times bigger (in your case around 50,000,000 operations).

1

In this formula O, the time value, is rarely 1. More importantly, for the time value may be different for different algorithms. An algorithm which scales linearly, O(n), may be significantly slower than an algorithm that scales quadratically, O(n2).

Knowing the Big O notation relative time values for different algorithms and expected sizes of n can help in picking the appropriate algorithm. For a small set a fast algorithm that scales non-linearly may be faster, than an alternate algorithm that scales linearly. If the set will always be small, then the algorithm with the smallest time value may be a better choice. An algorithm with a larger time value may be a better choice if the set is always going to be large. Some testing may be required to determine the break-even size. If the size is likely to vary, then the algorithm choice may be more difficult.

Additionally, algorithms that scale more linearly may be more complex than algorithms that scale less linearly. The added complexity is likely to increase costs and number of errors. This may factor in the choice of algorithm.

Consider sorting

  • The simplest bubble sort implementation has a complexity of O(n2). However it is simple and fast for small sets.
  • A common bubble sort be easily optimized by decrementing the size of the outer loop by 1 each iteration requiring with half the comparisons at the cost of a slightly slower outer loop. This can reduce the time value O to almost half that of the simplest bubble sore implementation. It still has a complexity of O(n2).
  • Tracking where any moves were done can drop the complexity of a bubble sort to O(n) for sorted input, but increases the time value.
  • Heap sort has a complexity of O(n log n) depending on the input set. However the time value is significantly higher that that of a bubble sort. For small n it will be slower, and is more complex to implement.
  • Other sort algorithms have different time values and scale differently. The complexity of implementation also varies.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.