Question

1Set up and solve a recurrence relation for the number of times the algorithm’s basic operation is executed.

2 How does this algorithm compare with the straightforward nonrecursive algorithm for computing this function?

Answer 1

1. A recurrence is an equation or inequality that describes a function in terms of its value on smaller inputs. Recurrences are generally used in divide-and-conquer paradigm.

Let us consider T(n) to be the running time on a problem of size n.

If the problem size is small enough, say n < c where c is a constant, the straightforward solution takes constant time, which is written as θ(1). If the division of the problem yields a number of sub-problems with size nbnb.

To solve the problem, the required time is a.T(n/b). If we consider the time required for division is D(n) and the time required for combining the results of sub-problems is C(n), the recurrence relation can be represented as −

The simplest form of a recurrence relation is the case where the next term depends only on the immediately previous term. If we denote the nnth term in the sequence by , such a recurrence relation is of the form

for some function . One such example is

A recurrence relation can also be higher order, where the term could depend not only on the previous term but also on earlier terms such as , , etc. A second order recurrence relation depends just on and and is of the form

for some function with two inputs. For example, the recurrence relation can generate the Fibonacci numbers.

To generate sequence basd on a recurrence relation, one must start with some initial values. For a first order recursion , one just needs to start with an initial value and can generate all remaining terms using the recurrence relation. For a second order recursion , one needs to begin with two values and . Higher order recurrence relations require correspondingly more initial values.

2.This is a command for fabionacci series using recursion

int fibo(int in){
 if(n <= 1){
  return n
 }else{
  return fibo(n-1) + fibo(n-2);
 }
}

This is a command for fabionacci series without using recursion

int fibo(int n){
 if(n <= 1){
  return n;
 }
 int fibo = 1;
 int fiboPrev = 1;
 for(int i = 2; i < n; ++i){
  int temp = fibo;
  fibo += fiboPrev;
  fiboPrev = temp;
 }
 return fibo;
}

You can clearly see in these commands the priors one is efficient in both time and space complexity.