Divide and Conquer alg that runs in constant time?

Question

Can you point out to me an example of a divide and conquer algorithm that runs in CONSTANT time! I'm in a "OMG! I can not think of any such thing" kind of situation. Point me to something please. Thanks

I know that an alg that follows the following recurence: T(n) = 2T(n/2) + n would be merge sort. We're dividing the problem into 2 subproblems - each of size n/2. Then we're taking n time to conquer everything back into one sorted array.

I also know that T(n) = T(n/2) + 1 would be binary search.

But what is T(n) = 1?

Answer 1

For a divide-and-conquer algorithm to run in constant time, it needs to do no more than a fixed amount of work on any input. Therefore, it can make at most a fixed number of recursive calls on any input, since if the number of calls was unbounded, the total work done would not be a constant. Moreover, it needs to do a constant amount of work across all those recursive calls.

This eliminates basically any reasonable-looking recurrence relation. Anything of the form

T(n) = aT(n / b) + O(n^k)

is immediately out of the question, because the number of recursive calls would grow as a function of the input n.

You could make some highly contrived divide-and-conquer algorithms that run in constant time. For example, consider this problem:

Return the first element of the input array.

This could technically be solved with divide-and-conquer by noting that

• The first element of a one-element array is equal to itself.
• The first element of an n-element array is the first element of the subarray of just the first element.

The recurrence is then

T(n) = T(1) + O(1)

T(1) = 1

As you can see, this is a very odd-looking recurrence, but it does work out.

I've never heard of anything like this coming up in practice, but if I think of anything I'll try to update this answer with details. (A note: I'm not expecting to ever update this answer. ^_^)

Hope this helps!