Binary search is very efficient, running in log (N) times, compared to linear se

Question

Binary search is very efficient, running in log (N) times, compared to linear search which is linear. On the other hand, binary search requires the elements to be presorted. How much time does it take to sort the elements? Both algorithms in the book, namely bubble sort and selection sort, yield square (N), or N*N, performance. In other words, one has to sort the elements in square (N) time and then search in Log (N) time. If we use linear search, it would have just taken N time. So, does it even make sense to have binary search

Explanation / Answer

Solution : Hey , Look , Binary search is worth to use when you want to search data in the same array multiple times , then it is worth to use sorting before searching instead of using linear search directly , because for every linear search you have to use O(n) time whereas if you use binary search. Then, You have to sort the all array element once with O(nlogn) time and then you can do searching using binary search with O(log n) time.

Example : Let you have 'n' elements in an array and you want to search elements 'n' times in that array. Then in binary search , you have to do sorting first which would require O(nlogn) time and then applying binary search would require O(logn) time. And applying binary search 'n' times for searching elements 'n' times would need O(n*logn) time.

So , total time consumed in sorting+binary search is O(nlogn)+O(n*logn) = O(nlogn)

Similarly , if you apply linear search for searching elements 'n' times in an array of 'n' elements. then , total time would be consumed is O(n*n) = O(n^2)

And it is very obvious that O(nlong) is much better than O(n^2).

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.