Question

Recursion is a technique for breaking down a complex problem into smaller pieces and then combining the results to obtain the desired answer. The most common example of recursion is calculating factorials. Describe another problem that can be solved using recursion and outline the approach using Java or Pseudo-Code. Discuss the Big-Oh run time performance of your example.

Answer 1

Here, I am using a Pseudo Code for Fibonacci function:-

int fib(int n) {

if(n <= 1) {

// base case

return 1;

} else {

// recursive case

return fib(n – 1) + fib(n – 2);

}

}

When computing big-O, we can make the following simplifications:

1. Eliminate any term whose contribution to the total is insignificant as N becomes large

o(n²+n) = o(n²) for large n

2. Eliminate any constant factors

o(3n) = o(n) for large n

The stragegy for computing Big-O depends on whether or not your program is recursive. For the case of iterative solutions, we try and count the number of executions that are performed. For the case of recursive solutions, we first try and compute the number of recursive calls that are performed.

Before going to solve the Big Oh, We must understand this concept:-

Gauss Summation:-

In many situations you have a case where you have a code block which executes 1 time, then 2 times, then 3 times until n times. In order to calculate the Big-O for code that follows this format we use the solution for the sum of an arithmetic series.

1 + 2 + 3 + . . . + (N - 2) + (N - 1) + N

= (N · (N + 1)) / 2

= (1 / 2) N² + (1 / 2) N

Which is

O( N² )

If we ask a question on the mid term where you need to compute the Big O of a recursive function it will be of the form where you simply need to calculate the number of calls in the recursion call tree. Often the number of calls is big O(b^d ) where b is the branching factor (worst case number of recursive calls for one execution of the function) and d is the depth of the tree (the longest path from the top of the tree to a base case).

Here is the call tree of Fib(5);

The branching factor is 2. The depth is n where n is the number on which the function is called. Thus the big O of this function is:

O( b^d ) = O( 2ⁿ )