time complexity after sorting and using binary search

Question

what will the time complexity be if I merge sort an array and apply a binary search function on it ? will it be O(log n)?

because

o(log n) + o(n log n) = O(log n)

Soerting is O(NlogN); you won't be able to reduce the time below that. And O(logN) + O(NlogN) = O(NlogN), not O(logN). — Jonathan Leffler
– Jonathan Leffler, Commented Jul 16, 2020 at 15:29
Is n*x, where n is an awfully large positive number and x is some positive number, larger than x by itself? Now, is n*x + x closer to n*x or x? — Antti Haapala
– Antti Haapala, Commented Jul 16, 2020 at 15:34
@JonathanLeffler do you have any idea or hints at how you can search for an element with a time complexity of O(log n) — samm
– samm, Commented Jul 16, 2020 at 15:39
If you start with sorted data and maintain it as data is added and removed, then you won't have to perform a sort before searching. — Christian Gibbons
– Christian Gibbons, Commented Jul 16, 2020 at 15:49
@ChristianGibbons i have an UNSORTED array and i want to find an element in the array with a time complexity of O(log n) — samm
– samm, Commented Jul 16, 2020 at 15:53

Lorena Mendes · Accepted Answer · 2020-07-16 23:20:40Z

1

Indeed, the time complexity for Merge Sort, in the average case, is O(n log n). The one for Binary Search is O(log n).

Adding both methods, you have a complexity of O(n log n) instead of the one you said. Imagine that you are adding 1(log n) + n(log n), which is n+1(log n) --> (n log n).

answered Jul 16, 2020 at 23:20

Lorena Mendes

496 bronze badges

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

Collectives™ on Stack Overflow

time complexity after sorting and using binary search

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related