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)$.

  • Maybe proving a kernelization lower bound would do the trick en.wikipedia.org/wiki/Kernelization – Tyson Williams Oct 17 '14 at 15:22
  • The output size is a lower bound on the running time. Thus any problem with output size matching its complexity has this property. – Chao Xu Oct 17 '14 at 15:53
  • @Chao Xu: Why doesn’t your argument apply to the input size? I think that the argument depends on which cost model (and computational model) we consider. – Tsuyoshi Ito Oct 18 '14 at 2:31
  • 2
    This is the opposite of what you're looking for, but given those oracles your model can solve subset sum - a known NP-Complete problem - in linear time, thus assuming P!=NP it's much more powerful than iterative functions in this case. The function would simply check if the current set adds to 0, then if not it calls itself on the n subsets of size n-1. The runtime itself is n! however, which is worse than brute force, so I'm not really sure how much value this model provides, but it's still an interesting question. – Phylliida Oct 18 '14 at 5:32
  • 2
    Your recent edit ("recursive" -> "divide-and-conquer") is a pretty big change to the question. I would just post a separate question instead. We can probably say things about divide-and-conquer by looking for instance at the depths of circuits. – usul Oct 20 '14 at 13:25
up vote 8 down vote accepted

Is there a problem with an exponential algorithm which has no algorithm with polynomial recursive runtime?

Yes. Note that if a tally language has “recursive algorithm” with polynomial “recursive runtime,” then it is in P. There is a tally language in E∖P by a standard diagonalization argument.

Is there a problem which can be solved in time $f(n)$, but provably has no recursive algorithm with recursive runtime $o(f(n))$?

It may depend on the computational model, but I doubt this is known, given that the time hierarchy theorem for two-tape Turing machines is not powerful enough to distinguish, say, O(n2) time and o(n2) time even without giving the latter the constant-time access to the answers on smaller instances.


Random comments on your questions in this post:

  • I do not think that these questions are related to the usefulness of recursive programs, despite what the title of the post and your choice of terminology suggest. As BVMR wrote in an answer, recursions and iterations are equivalent in a certain sense. Instead, I think that the questions have a connection to the usefulness of the divide-and-conquer approach.
  • In complexity theory, a related notion to your notion of “recursive algorithms” with their “recursive runtime” is called “length-decreasing self-reductions” with their time complexity.
  • Some part of your questions (definitely the part referring to sublinear-time algorithms) depend on the choice of computational model.
  • Regarding your first answer: let me try to expand it to see if I understand correctly. Assume that a certain tally language has an algorithm with polynomial "recursive runtime". A polynomial algorithm for this language can be constructed using dynamic programming. The answer for $n=0$ can be found in polynomial time since no recursive calls are required. The answer for $n=1$ can then be found in polynomial time using the answer for $n=0$. Then answer for $n=2$ can be found in polynomial time using the answers for $n=1$ and $n=0$, etc. Is this correct? – Erel Segal-Halevi Oct 18 '14 at 20:18
  • Yes, although it is better to avoid asymptotic notions such as “polynomial time” when you talk about a particular value of n; for example, it does not make sense to say “the algorithm runs in polynomial time when n=0.” If a tally language has a “recursive algorithm” with polynomial “recursive runtime” p(n), then we can compute the answer for n without the oracle by computing the answers for 0, 1, 2, …, n, and this takes time $O(\sum_{i=0}^n p(i))$, which is polynomial in n. – Tsuyoshi Ito Oct 18 '14 at 20:33
  • Thanks. I agree with your comment about divide-and-conquer and I edited the question accordingly. – Erel Segal-Halevi Oct 20 '14 at 7:30

Any question which has recursive answer has iterative answer and vice versa.

Any recursive algorithm can be rewritten in iterative way and vice versa.

Hence, your question doesn't stand good.

  • 4
    The complexity of an algorithm, as I defined it in the question, generally does not remain the same when it is converted from iterative to recursive. For example, the maximum of n elements can be found by an iterative algorithm with O(n) operations, but it can also be found by a recursive algorithm with O(1) operations (one of which is a recursive call). Although finally the runtime of both algorithms is the same, the recursive algorithm is simpler to program because it has less operations. – Erel Segal-Halevi Oct 17 '14 at 14:19

I am not sure if I correctly understand your notion of "recursive complexity".

Lets (reasonably) Assume a programming language that contains a schema for primitive recursion i.e. in which one can define functions $f$ from

$$ f(0,\vec x) = c(\vec x)\\ f(n+1,\vec x) = g(f(n,\vec x),n,\vec x) $$

where $c$ and $g$ are previously defined functions. Further let us assume that the basic functions (constants, projections, successor) have $\mathcal{O}(1)$ "recursive complexity" If I understand your definition correctly, then all primitive recursive functions (and thus problems/relations) have $\mathcal{O}(1)$ "recursive runtime". This, I think, can be seen by induction on the build up of recursive functions.

If all my assumptions are met, then the example you are looking for cannot be primitive recursive.

  • please elaborate on the downvotes – D.F.F Jan 11 '16 at 16:20
  • From the question, "The recursive runtime of that algorithm is calculated assuming an oracle which can solve $P(k)$ for every $k<n$ in constant time." . This definition of runtime gives naturally a rise to a complexity measure. This is a fancy way of saying that we do not care about the cost of lower size recursions, but only of the current step. So in your notation, we ask what is the complexity of comuting $g(f(n,x),n,x)$ given an oracle for $f(n,x)$ that has constant runtime. I didn't downvote you, but this is a year-old answered question and you also misinterpreted a given definition. – chazisop Jan 12 '16 at 9:08
  • thanks for your comment. I think I understood the definition. Since $g$ is a prim. rek. function, by induction hypothesis it has runtime $\mathcal{O}(1)$ since $f(n,x)$ is given by the oracle in constant time, evaluating the whole expression takes $\mathcal{O}(1\circ 1)=\mathcal{O}(1)$. – D.F.F Jan 12 '16 at 11:15
  • You have to use the full complexity for $g$, not its recursive complexity. That's not $O(1)$. – Emil Jeřábek Jan 14 '16 at 10:30
  • ahh, ok... now everything makes sense... thanks for the clarification... I was probably confused by the fact that recursive complexity is not invoked recursively^^ (which is not very celar from the definition imo) – D.F.F Jan 14 '16 at 10:40

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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