What is the time-complexity in a binary search?

Question

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?

You mean specifically the line if min1 < m2, what is the time complexity of that one line? Or are you asking about the time complexity of the entire function? — John Kugelman
– John Kugelman, Commented Oct 27, 2020 at 3:40
@JaeYing I didn't notice that your function is not actually a binary search. Your function is O(n). While min1 < min2 as a single expression is O(1). — Arty
– Arty, Commented Oct 27, 2020 at 3:49
@JaeYing It is called binary search, but actually inside each function call it does one comparison plus processes two parts of size n/2, both n in total size. So basically it doesn't halven the size of processed array as binary search does. — Arty
– Arty, Commented Oct 27, 2020 at 3:52

Thijs van Dien · Accepted Answer · 2020-10-27 03:57:12Z

5

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).

edited Oct 27, 2020 at 3:57

answered Oct 27, 2020 at 3:44

Thijs van Dien

6,6442 gold badges32 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

13 Comments

Frank Yellin Over a year ago

What is the time complexity of the splicing operation? Is it O(1) or O(n)? Depending on that, this algorithm is either O(n) or O(n log N).

Arty Over a year ago

@FrankYellin This algorithm builds a binary search tree. It has N leaves. And N-1 inner nodes. Only inner nodes operations are counted, comparison of min1 < min2, leaves don't do comparisons. So total complexity is O(N). Of cause it is somewhat amortized by recursive function calls operations. Slicing is also done inside inner nodes. So maybe precise complexity is around O(4N) which is simply O(N).

Frank Yellin Over a year ago

I suppose I'm unsure what the question is. What's the time complexity of this algorithm, or how many times is min1 < min2 called? O(n log n) and O(n), respectively (assuming the splice operation is O(<number of elements>).

Arty Over a year ago

@sabik Yes if it is python list which probably is then slicing is costly, if it is a numpy array which is probably not (because whole function is not numpy oriented) then it of cause lightweight.

Arty Over a year ago

@JaeYing BTW, your whole function can be replaced with just result = min(a) built in function call, it will be much more efficient in fact.

|

Collectives™ on Stack Overflow

What is the time-complexity in a binary search?

1 Answer 1

13 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

13 Comments

Your Answer

Sign up or log in

Post as a guest

Related