total time complexity of basic algorithm with binary search

Question

this may seem like a basic question about algorithms, but trying to confirm to myself that I'm correct (still trying to grasp basic concepts in teaching myself algortihms).

a problem i have requires first running an O(N) algorithm
then performing N binary searches on an N-element array
then running another O(N) algorithm

I'm trying to find the total time complexity for this problem.

Would it just be O(N) because that's the dominant order over O(logN)?

Thanks in advance

score 4 · Accepted Answer · 2014-08-03 20:32:25Z

4

An O(N) step would indeed dominate an O(log N) step. But your second step doesn't take O(log N) time. Each binary search takes O(log N) time and you perform binary search N times. So the second step, and thus the whole algorithm, takes O(N log N) time.

edited Aug 3, 2014 at 20:32

answered Aug 3, 2014 at 20:14

user395760

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

2 Comments

WycG Over a year ago

i originally actually thought you sum up the time complexities. so it would be O(n) + O (log n) + O(n) which is O(2n) + O(logn) with O(2n) as the dominant order. why is that thinking wrong? thanks!

user395760 Over a year ago

@WycG That rule is correct, your second term is wrong: It's not O(log n) but O(n log n) for reasons outlined above. n * O(log n) = O(log n) + O(log n) + ... + O(log n) = O(n log n) for the same reason O(n) + O(n) = O(2n), but a factor of 2 is ignored while a factor of n isn't.

Collectives™ on Stack Overflow

total time complexity of basic algorithm with binary search

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related