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

Answer 1

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.