CODEWITHSUNDEEP
algorithmsortingsearchbinary-search
Mandroid
Mandroid

Reputation: 7504

Binary search vs simple search

As per algorithm books, binary search's performance is O(log n) while for simple search it is O(n).

But why don't we also take into account the time spend in sorting which is a prerequisite for binary search?

Upvotes: 2

Views: 170

Answers (2)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476729

In short: because usually the constructing that list is only done once, whereas searching (and updating) is done multiple times.

Constructing a sorted list requires indeed O(n log n). The point of using binary search is that once the collection is sorted, we can perform multiple queries on that list, each with O(log n).

Furthermore if you use a binary search tree for example, you can perform insertion, and removal of elements in O(log n) as well, so updating the collection can be cheap as well (given you use an effective data structure for that).

In a database for example one frequently uses indexes to perform fast lookups. Usually the number of reads is large compared to the number of updates. Updating a single element requires O(log n), so creating the index on existing data is indeed expensive, but this is not very common compared to searching and updating a B-tree datastructure [wiki].

Upvotes: 3

Quentin
Quentin

Reputation: 943643

It is assumed that the data will be stored already sorted. Since the data doesn't need to be re-sorted each time a search is performed, it isn't accounted for in Big O.

Upvotes: 1

Related Questions