Computer Science Canada Big O notation of a recursive method |
| Author: | phunkypants [ Mon Mar 29, 2010 11:26 pm ] |
| Post subject: | Big O notation of a recursive method |
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); } } |
|
| Author: | Tony [ Mon Mar 29, 2010 11:49 pm ] |
| Post subject: | RE:Big O notation of a recursive method |
well, given an argument of value N, how many times would the if statement be evaluated? |
|
| Author: | chrisbrown [ Mon Mar 29, 2010 11:50 pm ] |
| Post subject: | RE:Big O notation of a recursive method |
Does it help if you assume that the runtime of rfib is O(1)? (Not that that's the answer, obviously). |
|
| Author: | phunkypants [ Tue Mar 30, 2010 12:00 am ] |
| Post subject: | RE:Big O notation of a recursive method |
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? |
|
| Author: | DemonWasp [ Tue Mar 30, 2010 1:45 am ] |
| Post subject: | RE:Big O notation of a recursive method |
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. |
|
| Author: | phunkypants [ Tue Mar 30, 2010 8:45 am ] |
| Post subject: | RE:Big O notation of a recursive method |
hmmm ic. Thanks for the help, ima try and figure it out. |
|
| Author: | Prabhakar Ragde [ Tue Mar 30, 2010 1:22 pm ] |
| Post subject: | RE:Big O notation of a recursive method |
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. |
|
| Author: | DemonWasp [ Tue Mar 30, 2010 7:58 pm ] |
| Post subject: | RE:Big O notation of a recursive method |
@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. |
|
| Author: | Prabhakar Ragde [ Tue Mar 30, 2010 8:21 pm ] |
| Post subject: | RE:Big O notation of a recursive method |
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.) |
|
| Author: | DemonWasp [ Wed Mar 31, 2010 1:01 am ] |
| Post subject: | RE:Big O notation of a recursive method |
Unfortunately, that was the part of CnO I never really understood. Graph theory is much more intuitive, and in my experience much more interesting. |
|