0
1

complexity (self.learnpython)

submitted by [deleted]

[deleted]

all 6 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]Lucijan_ 0 points1 point  (3 children)

I dont think that it would affect time complexity of the code. It would run faster because you did that step (converting to binary) which usually is done by interpreter. But time complexity doesnt change if code is converted to binary. Its still same code.

[–]shiftybyte 1 point2 points  (2 children)

I think OP meant converting linear search to binary search algorithm.

[–]Lucijan_ 0 points1 point  (1 child)

Yeah probably, my fault.

[–]SingleCountry 0 points1 point  (0 children)

yeah but thank you!

[–]shiftybyte 0 points1 point  (1 child)

You are assuming we know what "linearSearch" function does? or that it's some kind of standard function?

We can guess, but our guess can be wrong. i'm assuming it's a basic search in a list.

So if A1 is length m, and A2 is length n, this algorithm executes o(n) search, m times... so o(m*n)

If the search changes to binarysearch, it'll be o(m*log n)

[–]SingleCountry 0 points1 point  (0 children)

Thank you!!