What is the complexity of bisect algorithm?

I wrote code to understand which of them is faster when it comes to search an element in a list. It turns out to be bisect. What I do not understand is what is complexity of bisect algorithm and does it use Van Emde Boas tree?

#python inbuilt list search using 'in' took 0.0702499200317 secs
def mul3(): a = [1, 2, 4, 5, 6, 7, 8, 10, 12, 42, 55, 65, 69, 95, 96, 101, 156, 199] for x in a: if x in a: print x, "True" else: print x, "False"
#using bisect took 0.0649611193601
def mul4(): a = [1, 2, 4, 5, 6, 7, 8, 10, 12, 42, 55, 65, 69, 95, 96, 101, 156, 199] import bisect for x in a: locate = bisect.bisect_left(a, x) if locate == len(a) or a[locate] != x: print False print True #using binary search took 0.0651483638284
a = [1, 2, 4, 5, 6, 7, 8, 10, 12, 42, 55, 65, 69, 95, 96, 101, 156, 199]
for x in a: lo = 0 hi = 18 while lo < hi: mid = (lo+hi)//2 midval = a[mid] if midval < x: lo = mid+1 elif midval > x: hi = mid else: print True lo = hi

Reference:

2 Answers

It uses binary search, which makes it O(log n).

There is binary search, right. O(Ln(n)) is the answer.

But, your list is not sufficient to test all the cases. All algorithms may took different execution times, but you have to test these with all the cases. If you test with enough many lists, you will get the right results.

I hope you're convinced.