CODEWITHSUNDEEP
pythontime-complexitybig-obinary-search
Nix
Nix

Reputation: 143

What is the time-complexity in a binary search?

def binsearch(a):
    if len(a) == 1:
        return a[0]
    else:
        mid = len(a)//2
        min1 = binsearch(a[0:mid])
        min2 = binsearch(a[mid:len(a)])
        if min1 < min2:
            return min1
        else:
            return min2

I have tried to come up the time-complexity for min1 < min2 and I feel that it is O(n) but I am not very sure if it's correct. Could someone please try to explain to me how to calculate time-complexity for such code?

Upvotes: 1

Views: 425

Answers (1)

Thijs van Dien
Thijs van Dien

Reputation: 6616

If min1 and min2 are numbers, and there's always 2 (a constant) of them, the amount of work on that particular line (a single comparison) never changes. Therefore its time complexity is O(1).

What may change, however, is the number of times that line is executed! When you have n times an O(1) operation, the overall time complexity is still O(n).

Upvotes: 5

Related Questions