When we try to construct an algorithm for a new problem, divide-and-conquer (using recursion) is one of the first approaches that we try. But in some cases, this approach seems fruitless as the problem becomes much more complicated as its input grows.
My question is: are there problems for which we can prove that a divide-and-conquer approach cannot help to solve? In the following lines I try to make this more formal.
Let $P(n)$ be a certain problem whose input has size $n$ (e.g. a problem that accepts an input an array of $n$ numbers). Suppose we have a recursive algorithm for solving $P(n)$. The recursive runtime of that algorithm is calculated assuming an oracle which can solve $P(k)$ for every $k<n$ in constant time. For example:
- The recursive runtime of binary search is $O(1)$, since it uses only a comparison and two recursive calls.
- The maximum element in an array can be found in recursive time $O(1)$.
- The recursive runtime of merge sort is $O(n)$, because of the merging step.
The recursive time is usually smaller than the actual runtime, which reflects the fact that the recursive algorithm is simpler than a straightforward non-recursive solution to the same problem.
Now my question is:
Is there a problem which can be solved in time $f(n)$, but provably has no recursive algorithm with recursive runtime asymptotically less than $f(n)$?
Some specific variants of this question are:
- Is there a problem in $P$ which has no algorithm with recursive runtime $O(1)$? (Maybe sorting?)
- Is there a problem with an exponential algorithm which has no algorithm with polynomial recursive runtime?
EDIT: contrary to my guess, sorting has an algorithm with recursive runtime $O(1)$. So it is still open, whether there a problem in $P$ which has no algorithm with recursive runtime $O(1)$.