0

$$f(1) = 1 : f(n)=f(n-1)+f(\lceil n/2\rceil)+1$$ What is the computational complexity of this recursive function? I have not been able to find anyone explaining a function like it in my searching, and I'm completely stuck as to what to do with it.

It seems like it should be exponential, but if you try to substitute that you get $$2^{n-1}+2^{n/2}+1<2^n$$ But it also must be greater than polynomial, since $$(n/2)^k+(n-1)^k=n^k/2^k+n^k-{k \choose 2}n^{k-1}+{k \choose 3}n^{k-2}-{k \choose 4}n^{k-3}...>n^k$$ Edit: I am NOT asking for you to redefine the function so that it can be calculated more efficiently, I already know that can be done in linear time. I am asking what the complexity of the function as written is. You can't take the recursive function and redefine it in a non-recursive way because that changes its complexity.
If I had told you the function was $f(x)=2f(x-1)$ I'm sure you'd have happily jumped at the chance to tell me it's exponential, you wouldn't say it's constant because it can be calculated using a single bitshift operation. Some examples.

Erik
  • 1
  • I assume $n$ is integer? If so, how do we treat odd numbers? Do we, for example, need $f(\frac{1}{2})$ in order to calculate $f(3)$ ? – Saeed Dec 18 '20 at 21:51
  • @Saeed Sorry, it's meant to be rounded up. – Erik Dec 18 '20 at 21:57
  • I think your argument that the complexity is greater than polynomial is flawed. A memoizing algorithm should be able to compute $f$ in polynomial time. – Rob Arthan Dec 18 '20 at 22:28
  • @RobArthan I know that the value of f(n) can be calculated in linear time. The question isn't about how you'd calculate f(n) programmatically, it's about what the value of f(n) itself looks like for large n. – Erik Dec 18 '20 at 22:34
  • Well then please edit your question to explain what you actually mean. You are using the term "complexity" in a non-standard way. – Rob Arthan Dec 18 '20 at 22:40
  • @RobArthran then what am I supposed to call it? I wrote down a function, and I want to know what it asymptotically approaches as n goes to infinity, that sounds like complexity to me. And I can see other questions on this site using the same language. – Erik Dec 18 '20 at 22:57
  • "Asymptotic behaviour" is a better term. When analyzing computational complexity, that's also a question of asymptotic behaviour, but then the question isn't "How large does the thing become?" but rather "How much work does it take to compute the thing?" Of course, you can put a formula to how much work out takes to compute your thing, and by then the issue of computational complexity will look very much like your question here. But it is, in a sense, one abstraction level above what you seem to be after. – Arthur Dec 18 '20 at 23:36
  • @Eirk: I think you mean "asymptotic behaviour" as suggested by Arthur. "Complexity" isn't the right word. – Rob Arthan Dec 19 '20 at 00:03

1 Answers1

0

First thoughts: a worst case scenario is that in order to calculate $f(n)$ you need to calculate $f()$ of all integers from $1$ to $n$. That is $n$ calculations, and each of those calculations is $O(1)$ , because if you consider that you are building the sequence from bottom up then for each $f(n)$ line, you have previously calculated $f(n-1)$ and $f(\lceil \frac{n}{2} \rceil)$ . In this sense, the complexity of this recursive function should be $O(n)$ .

Second thoughts: you might even be able to find that the worst case is not as bad as we reviewed in the above paragraph (although I doubt that, because for each $n$ we need $f(n-1)$ ).

Edit: Based on the new details added in an edit to the text of the problem, I believe the problem is not asking for computational complexity as meant when using the O-notation. Rather, it is asking for an approximate but explicit form of the given recursive function.

Saeed
  • 1,872
  • I believe that what is meant to be found is the rate at which $f(x)$ grows, judging from the calculations in the question. – Joshua Wang Dec 19 '20 at 01:32
  • Ah, in that case my argument would not apply. My assumption for using the O-notation is based on the expression "computational complexity" in the text of the problem. – Saeed Dec 19 '20 at 03:36
  • @Saeed I don't have an issue with you using big O notation. But if I ask about a recursive function, you can't replace it with a different, non-recursive function because that will obviously change its complexity, even if it returns the same value. – Erik Dec 19 '20 at 15:23
  • I just edited my own answer and got your comment at the same time! Finding the explicit, or non-recursive, form is always an interesting problem. – Saeed Dec 19 '20 at 15:27
  • @Erik, you seem to be confusing function with algorithm. If two algorithms return the same value for every input, they are computing the same function. (And when you say recursive, I think you mean recursively defined. And so on...) – TonyK Dec 19 '20 at 15:42