-4

We are programming in C as part of our semester and this is an example of a colloquim test question:

unsigned f(unsigned n) {
if(n<=1) return 1;
return f(n-2)+f(n-2);
}

How does the stackframe look for this function if I called it for f(4) and what is the Big Theta of it (does return f(n-2) + f(n-2) count as 2 calls of the same function or as 1)

Perke
  • 1
  • 1
    This isn't quite Fibonacci, unless there's a typo--both terms are `f(n-2)` instead of `f(n-1)` and `f(n-2)`. The way it's written means that the time doubles for each increment of 2; might be theta(2 ^ (n / 2)) – Mike P Apr 14 '18 at 00:01
  • Apologies, my mistake. – meowgoesthedog Apr 14 '18 at 00:02
  • I suspect a typo; otherwise this is just `return 1 << (n >> 1);` – Jeff Learman Apr 14 '18 at 00:08
  • *does return f(n-2) + f(n-2) count as 2 calls of the same function or as 1* it counts as 2, you are calling `f(n-2)` twice. If your function, as part of optimization, would cache the values, then you could that as one. But your function as it is, does not cache values, so yes, you have to count it as 2. – Pablo Apr 14 '18 at 00:20

1 Answers1

1

The question "what does the stack frame look like?" doesn't have a single answer. The answer depends on at what point we look at the stack frame.

The sequence of calls looks like this:

f(4)
  f(2)
    f(0)
    f(0)
  f(2)
    f(0)
    f(0)

If we set a breakpoint at the return for when n <= 1 and called f(4), we'd hit the breakpoint inside the first call to f(0) in the sequence above. The stack frame would look something like this (assuming stack grows from top of allocated frame downward, and we're dumping memory from the SP to sequentially higher memory, both of which are typical):

0
PC of f(0) call
2
PC of f(2) call
4
PC of f(4) call

For this function, bigO is the same as big theta, and I believe Mike P got it right: 2^(n/2). To see why, try writing the call sequence for f(6) and f(8) and hopefully you'll see the pattern: every time you add two to the parameter, the number of calls doubles.

For a more complete answer, see Computational complexity of Fibonacci Sequence . This is not the Fibonacci series, but the algorithm has the same complexity.

Jeff Learman
  • 2,914
  • 1
  • 22
  • 31
  • Thank you all for the answers, actually really helpful, the reason I did not look at Fibonnaci one as a great example is because my question is about f(n-2) that happens twice instead of f(n-1) and f(n-2), so my confusion came about how many times will it call the function – Perke Apr 14 '18 at 00:51
  • You're welcome and welcome to Stack Overflow. Please accept the answer if it answers your question. Also, please "up-vote" any comments that were helpful to you. That's how we express "thanks" here at SO. – Jeff Learman Apr 16 '18 at 15:37