24 Jan 2023, 10:39 PM

Best Conceivable Runtime (BCR)

The Best Conceivable Runtime is the best runtime you could conceive of a solution to a problem having.

Example

You want to compute the number of elements that two arrays have in common. You already know that you can't do better than $O (A + B)$ time because you have to "touch" each element in each array. $O (A + B)$ is the BCR.

Be careful!

Suppose you have to find all pairs with sum k within an array.
It's wrong to say that you can't do better of $O (N^{2})$ because you have to look at $N^{2}$ pairs. See Pairs of Integers with difference k

Remember that the best conceivable runtime is not necessarily achievable. It says only that you can't do better than it.
Last thing, if you ever reach the BCR and have $O (1)$ additional space, then you know that you can't optimize the big O time or space.
Here an example of how to use BCR.