Big O notation of a recursive method

[phunkypants]

I'm trying to figure out what the big O notation of this method is in regards to n. Any help is appreciated

public static long rfib(long n) {

if ((n == 1) || (n == 2)) {
return 1;
} else {
return rfib(n - 1) + rfib(n - 2);
}
}

[Tony]

well, given an argument of value N, how many times would the if statement be evaluated?

[chrisbrown]

Does it help if you assume that the runtime of rfib is O(1)? (Not that that's the answer, obviously).

[phunkypants]

Ya I know that the method on its own is O(1). But its recursive - and I don't really know how to go about figuring out the time complexity

Tony @ Mon Mar 29, 2010 11:49 pm wrote:

well, given an argument of value N, how many times would the if statement be evaluated?

I guess its always evaluated once right? But since its recursive the method, how does that change the big o notation?

[DemonWasp]

You have one invocation of fib ( N ).

That causes one invocation each of fib ( N-1 ) and fib ( N-2 ).

Those cause a total of 4 invocations: fib ( N-2 ), fib ( N-3 ), fib ( N-3 ), fib ( N-4 ).

You can probably imagine that the next iteration results in 8 invocations.

You may have sensed a pattern here. Recall your sum-of-series work (this is Grade 11-12 Algebra) and you should find an answer easily enough.

It's worth noting that there are a lot of more advanced methods for finding the runtime for a recursive algorithm that isn't as well-behaved as your fibonacci example, and these include The Master Method / Theorem. This is something like 3rd-year-CS-degree material, however.

[phunkypants]

hmmm ic. Thanks for the help, ima try and figure it out.

[Prabhakar Ragde]

DemonWasp: your pattern breaks if N=3.

In general, you need to set up and solve a recurrence:

T(0) = a
T(n) = T(n-1) + T(n-2) + b

You can bound T(n) from above in terms of F(n), if you are careful about it.

[DemonWasp]

@Prab: While that's true (in fact, the pattern I provided is not correct for a lot of other inputs: N = 4, 5, 6, 7...), it does provide an upper bound on the number of invocations, albeit an extremely loose one. I could have dug out my CS341 notes and figured out exactly what the value of that recurrence is, but I suspected that wouldn't help the OP much.


Perhaps more helpful:

fib ( 1 ) is one invocation
fib ( 2 ) is one invocation
fib ( 3 ) is three ( one for fib(1), one for fib(2), one for the "parent" invocation itself, fib(3) ).
fib ( 4 ) is five ( one for fib(2), three for fib(3), one for the "parent" invocation itself, fib(4) ).
fib ( 5 ) is nine ( three for fib(3), five for fib(4), one for the "parent" invocation itself, fib(5) ).

This will give you the recurrence Prabhakar is talking about.

[Prabhakar Ragde]

CS 341 won't help you with that recurrence; it is somewhat specialized. Mostly because no one actually computes anything this way. (If you remember the first few weeks of Math 239, they might help.)

[DemonWasp]

Unfortunately, that was the part of CnO I never really understood. Graph theory is much more intuitive, and in my experience much more interesting.