8
$\begingroup$

Let's say we want to find the smallest positive integer x for which some property A holds. We know that such an integer exists. However, we have no knowledge about the scale of x (i.e. x could be 7 or 5'142 or 17 Quadrillion or whatever).

We have a function f that returns true when evaluated at values larger or equal to x, f returns false when evaluated at values strictly smaller than x. Let's assume evaluating f at n has a runtime complexity of $O(n^2)$.

What is a reasonable (or even optimal) way of selecting integers to evaluate f at in order to find x while reducing runtime? How would the answer change when the runtime complexity of f is different?

My thoughts:

Usually I would calculate the expected number of calculations needed and try to minimize that value. However, without any knowledge about the size of x I could not wrap my head around how I would do that since a uniform distribution over all positive does not make a lot of sense. Is there another type of distribution that can be used in such cases? Further it does not make sense to me to evaluate every integer in increasing order until x is found. Intuitively, I would probably evaluate powers of 10 (i.e. f(10), f(100), f(1000)), but this is surely not optimal.

Any thoughts are appreciated, even just the keyword that would lead to successful google results.

$\endgroup$
3
  • 3
    $\begingroup$ If you have a priori distribution for x, then you can write a binary search that splits the search-space in two subsets of equal probability. If you don't, the most usual approach is what you suggest, use a geometric sequence (such as the powers of 10 or the powers of 2); which is equivalent to a binary search that assumes that x follows a geometric distribution. $\endgroup$
    – Stef
    Aug 11 at 12:13
  • 2
    $\begingroup$ Your intuition is right in this case. That's the best method we can get :) $\endgroup$
    – justhalf
    Aug 11 at 20:20
  • $\begingroup$ Also, the difference between going with powers of 10 or going with powers of 2 is about 3 calls to f. That's not even Θ(n) calls to f. That's just O(1) calls to f. So the exact sampling method doesn't matter too much. $\endgroup$
    – Stef
    Aug 12 at 12:19

3 Answers 3

9
$\begingroup$

The normal approach is to evaluate $f(1)$, $f(2)$, $f(4)$, $f(8)$, $f(16)$, $f(32)$, $f(64)$, etc., until you find the first power of two for which $f(2^k)=\text{true}$ (and thus $f(2^{k-1})=\text{false}$). Then, you use binary search in the range $[2^{k-1},2^k]$ to find the smallest value for which f returns true.

If the correct answer is $n$, the first stage will take $O(n^2)$ time, and the second stage will take $O(n^2 \log n)$ time, for a total running time of $O(n^2 \log n)$.

As gnasher729 indicates, if you care about the constant factors, you can optimize this by replacing 2 with an appropriate constant.

This process is sometimes called doubling search. See https://en.wikipedia.org/wiki/Exponential_search and https://en.wikipedia.org/wiki/Binary_search_algorithm.

$\endgroup$
3
  • 1
    $\begingroup$ Maybe this is a dumb question, but how is the first step O(N^2)? It seems like it ought to be O(log(N)) (and the entry you link for Exponential Search also claims O(log(N))). Likewise, the second step is a binary search over an interval of N/2, so it should have a complexity of log(N). Where are you getting the factors of N^2? $\endgroup$
    – Nobody
    Aug 11 at 16:42
  • 7
    $\begingroup$ @Nobody, from the question: "Let's assume evaluating f at n has a runtime complexity of $O(n^2)$." I am counting the runtime complexity, not the number of times we need to evaluate f. $\endgroup$
    – D.W.
    Aug 11 at 17:12
  • 2
    $\begingroup$ Ah, I had missed that part, thanks. $\endgroup$
    – Nobody
    Aug 11 at 19:05
12
$\begingroup$

Linear search is $0,1,2,3,4,\cdots k,\cdots$. ($O(n)$ steps to pass $n$.)

Exponential search is $1,2,4,8,16,\cdots2^k,\cdots$. ($O(\lg(n))$ steps to pass $n$.)

Doubly exponential search is $2,4,16,256,65536,\cdots2^{2^k},\cdots$. ($O(\lg(\lg(n)))$ steps to pass $n$.)

And so on.

After you have found a $\text{true}$, you can continue with dichotomic searches at the previous growth levels.

If you expect truly huge numbers, you can use even faster growing sequences, such as $2\uparrow^k2$. ($O(\lg^*(n))$ steps to pass $n$.)

There is no theoretical optimum.

$\endgroup$
6
  • 1
    $\begingroup$ Assuming evaluating $f$ at $n$ has a runtime complexity of $\Theta(n^2)$, the exponential search is $\Theta(n^2)$-time. However the double exponential search is not $O(n^3)$-time. That is, double exponential search could be considered as worse than exponential search. $\endgroup$
    – John L.
    Aug 13 at 3:59
  • $\begingroup$ @JohnL.: "the double exponential search is not $O(n^3)$ time". This is obvious. And ? $\endgroup$ Aug 13 at 11:30
  • $\begingroup$ A very fast-growing search will on average overshoot by more, and leave a large range to binary search. (Or to scale back to exponential from that point). Also potentially doing a very expensive evaluation at the largest n. $\endgroup$ Aug 13 at 12:08
  • $\begingroup$ @PeterCordes: the large range is not addressed by binary search, but by the previous growth level (recursively); this will not be costly. What do you mean by "a very expensive evaluation at the largest n" ? $\endgroup$ Aug 13 at 12:12
  • 2
    $\begingroup$ If you overshoot by many orders of magnitude, say f(1 trillion) when exponential growth would have only evaluated f( 1 million), you're paying for O(1 trillion ^ 2) instead of say O(1M^2 + 100k^2 + 10k^2 + ...). Since O(n^2) grows polynomially, even just exponential growth is enough to make the cost of smaller evaluations not very significant. (I used base 10 growth just for example.) $\endgroup$ Aug 13 at 12:17
7
$\begingroup$

If you want the exact value of x, you’d find an interval of width 2^k containing x, then k steps of binary search at a cost of roughly x^2 find x. Total cost about x^2 log x.

If you want a rough estimate for x, you’d evaluate at x = c^n for a suitable c > 1. The cost is multiplied by c^2 for each n, so the total cost is c^2n * (c^2 / (c^2 - 1)).

C^2n = d*x for some d, 1 <= d < c^2. You can calculate the expected value of d^2, multiplied by c^2 / (c^2-1) and pick c to minimise this factor.

$\endgroup$

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.