Search code examples
pythonalgorithmbig-obisection

python bisect is O(n^2)?

I'm running a simple test to monitor how long does it take to sort-insert into a list with the bisect library

import numpy as np
import bisect

def get_time(N):
    myl = []
    a = time.time()
    for i in np.arange(N):
        bisect.insort_left(myl, random.randint(0,1000000) )
    b = time.time()
    return (b-a)

So I call this with:

t_dict = {}
for N in [1000,5000,10000,50000,100000,200000,300000,400000,500000]:
    t_dict[N] = get_time(N)

and plot the results:

enter image description here

I would have guessed/hoped that insort would be at max O(nlog(n)). From the documentation, one reads:

"Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step."

What am I missing here?

EDIT: I was missing something extremely obvious. Anyway, I would like to update the question with the same thing using SortedList from the package SortedContainers:

enter image description here

very fast stuff!

Solution

  • bisect is O(logN). However, insertion into a list is O(N). You do that N times.

    From the bisect.insort_left() documentation:

    Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.

    So insertion is still O(N), the O(logN) search time is (asymptotically speaking) insignificant compared to that. So overall, your timed tests are taking N times O(N) == O(N^2) time.