14

I recently asked a question on CodeReview SE where using a binary search was recommended, and the author of the answer proved that it was faster than my implementation. During my research on the topic, I came across a table that shows the complexities of a binary search:

These are the complexities of a binary search −

Worst-case Best-case Average Worst-case space complexity
O(log n) O(1) O(log n) O(1)

I think I'm misunderstanding the information this table is meant to relay. I'm perceiving it as:

The average performance of a binary search is the worst-case performance.

However, if this were true, wouldn't a binary search be avoided in many cases? I'm new to this level of optimization so my impediment could just be some underlying prerequisite that I don't have knowledge of yet.

Edit: For clarity in hindsight, the question I sought answers to is below this edit. The one above it is strictly a questioning of my reasoning during my research phase that I included to demonstrate my lack of understanding. My apologies for any confusion on the matter.


What is meant by "the complexities of a binary search", what are those complexities, and what is this table actually telling me relative to those complexities?

9
  • 15
    This question is strange: you don't favor X over Y just because X has some properties (in isolation). You favor X over Y because X has some properties which give an advantage when compared to the related properties of Y. But in your case, you did not even mention "Y", so why should one avoid X?
    – Doc Brown
    Oct 5 at 18:56
  • 15
  • 1
    @DocBrown I'm not asking why binary searching is faster, nor if I should favor it over my currently implemented solution. I'm asking what is meant by complexity, what those complexities are in binary searching, and what the table posted conveys, related to that information. As such, the Y is irrelevant to my question. Oct 5 at 19:05
  • 6
    It's poor terminology or poor writing. They are referring to the computational complexity, given in Big-O notation.
    – user207421
    Oct 6 at 3:39
  • 2
    @user207421 lack of knowledge and as a result, poor terminology. I'm self taught and just never needed to know this level of detail when it comes to optimization. As such, I had never heard about time complexity prior to the research that fueled this post. Oct 6 at 15:36
40

The full term for this is "Time Complexity" and you'll want to use that if you are searching. This is a core concept in computer science. I am not going to attempt to explain it in detail but here's a high-level explanation:

The idea of time complexity is to understand how the performance of an algorithm relates to its input size(s). A time complexity of O(1) means 'constant time'. In other words, the performance of the algorithm doesn't change with the size of the input. I think in this case, the best case is when the item you are looking for happens to be the middle item (the first one examined). Best case performance tends to be the least interesting or useful of these measures in my experience - with the exception of when the best case is really bad.

O(log n) means that the time it takes is related to a logarithm of the input. In this case the base of that is 2. So if the list has 16 elements, it will take on average about 4 checks to find an item. If the list has 30,000 elements, on average you should expect it take something like 15 checks.

The fact that the worst case is the same as the average means that you'll never need more than that many log₂(n) checks to find something. It could be better but it will never be worse. That's actually a good thing. Some algorithms have good average times but really bad worst case scenarios. That makes it hard to predict performance in practice. It's like driving on a freeway; it might be the fastest route most of the time but if there's a bad wreck, you could be stuck for hours. If you want to make sure you get somewhere on time, you might be better off with a slower (on average) route that is more predictable.

Addendum: I failed to address the 'space complexity' entry in the table. This is a very similar concept to 'time complexity' (or more properly 'computational complexity') except that it refers to the amount of memory or storage that is required to execute the algorithm. In this case, it's constant which essentially means it doesn't take anymore memory (or other storage) to search a list of a billion items than it does to search one of 16 items. The lists themselves obviously do, but the memory allocated to the execution of the search algorithm remains the same. In other algorithms, however, it's not uncommon to trade space for time e.g. an index on a database table requires extra storage but can greatly improve the performance of lookups.

23
  • 9
    As an example for a similar data structure with worse worst-case complexity, consider hash tables: O(1) typical lookup speed (most of the time, can find correct element immediately), but O(n) worst case (might have to search all elements).
    – amon
    Oct 5 at 17:35
  • 2
    @amon Yes exactly. If your hashing algorithm is bad, it devolves into a linear search of an unsorted list.
    – JimmyJames
    Oct 5 at 17:37
  • 3
    Adding to the fun, it's often also helpful to look at the prerequisites of an algorithm. Binary search is O(log n), but it requires that the input be sorted first. A linear search of an unsorted list is O(n), but it (obviously) doesn't require that the input be sorted. And, that's before real-world complications kick in, too.
    – minnmass
    Oct 6 at 4:37
  • 3
    I think you've made an error with the example - with 16 elements, the worst-case will examine 4 of them; the average case almost 3 (and both scale proportionally to log n, but with different constants of proportion). Oct 6 at 15:04
  • 5
    I guess the key point is that average and worst-case scale the same way, but average is usually some fraction of worst-case. Oct 6 at 15:36
8

The average time is smaller than the worst-case time, because the search can terminate early, but this manifests as a constant factor, and the runtime is in the same complexity class.

Using a linear search in a sorted array as an example: the search terminates when a greater or equal element has been found. The worst case requires N comparisons, the average case fewer than that. If the array is just the range [1..1000], and we are looking for a random number in that range, we will on average use 500 comparisons per lookup, i.e. N/2.

From a complexity point of view, this constant factor does not matter, and it is omitted, so the average lookup time is still O(N).

The same happens for the average lookup time in binary searches.

6

The data in this table is not telling you how long a search takes. Its telling you how the time and storage may scale with the amount of data being searched.

Lets take a real world example. Suppose you're google, or twitter, or wikipedia, or github. Or some project/research that searches large lists. Someone enters a search term. You have a vast amount of data to search. You do not want to use a search method thats great for small lists (search spaces) but totally unfeasible for huge ones. What you want to know is, as the size of your data grows, the extra time needed to search the larger database/list stays broadly "reasonable".

Examples of scalings might be:

  • O(1) - as your data gets huge, searches will broadly stay unchanged.

  • O(n) - as you double your data size, you'll have to do twice as many checks to find an item. Increase database by a thousand times, searches will involve of the order of a thousand times as many checks to find an item.

  • O(n2) - as you double your data size, you'll have to do 4 as many checks to find an item. Increase database by a thousand times, searches will involve of the order of a million times as many checks to find an item.

  • O(log2n) - as you double your data size, you'll have to do 1 extra check to find an item. Increase database by a thousand times, searches will involve of the order of a 10 more checks to find an item. (log21000 is about 10)

None of this says which is faster:

So for example if your list has 5 items, then looking at the 5 in turn may be your fastest search strategy. If it has 500 million items then some other search method will be better.

So you could have a search strategy O(n) that takes say, 1 millisecond to search 1000 items, 1 second to search a million items, 20 minutes (about 1000 seconds) to search a billion items.

But you might also have a second search strategy that's O(log2n), that takes 500 milliseconds to search 1000 items. That's so slow, compared to the first search strategy. But because it scales differently, it might only take 1 second to search 1 million items, and 1.5 seconds to search a billion items.

(Because log2 of a million is roughly 2 x log2 of a thousand, and log2 of a billion is roughly 3 x log2 of a thousand)

2
  • 1
    To expand on your last section: It's possible for an algorithm to be theoretically "faster" than another in terms of its Big-O classification, but useless in practice because the n required is larger than can possibly fit in a computer's memory. In which case it's called a galactic algorithm.
    – dan04
    Oct 7 at 0:25
  • 1
    As an example, in actual use, the Scala core library supports immutable sets, and since they are immutable, a set of size 4 uses a class that handles sets of exactly size 4, with linear search instead of hashing or binary search.
    – prosfilaes
    Oct 7 at 7:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.