Use the divideandconquer approach to write a recursive algor

Use the divide-and-conquer approach to write a recursive algorithm that computes n!. Define the input size (see Exercise 36 in Chapter 1), and answer the following questions. Does your function have an exponential time complexity? Does this violate the statement of case 1 given in Section 2.8?

2.8 When Not to Use Divide-and-Conquer If possible, we should avoid divide-and-conquer in the following two cases: 1. An instance of size n is divided into two or more instances each almost of size n 2. An instance of size n is divided into almost n instances of size n/c, where c is a constant. The first partitioning leads to an exponential-time algorithm, where the second leads to a n% n) algorithm. Neither of these is acceptable for large values of n. Intuitively, we can see why such partitionings lead to poor performance. For example, the first case would be like Napoleon dividing an opposing army of 30,000 soldiers into two armies of 29,999 soldiers (if this were somehow possible). Rather than dividing his enemy, he has almost doubled their number! If Napoleon did this, he would have met his Waterloo much sooner. As you should now verify, Algorithm 1.6 (nth Fibonacci Term, Recursive) is a divide- and-conquer algorithm that divides the instance that computes the nth term into two instances that compute respectively the (n - 1)st term and the (n - 2)nd term. Although n is not the input size in that algorithm, the situation is the same as that just described concerning input size That is, the number of terms computed by Algorithm 1.6 is exponential in n, whereas the number of terms computed by Algorithm 1.7 (nth Fibonacci Term, Iterative) is linear Sometimes, on the other hand, a problem requires exponentiality, and in such a case there is no reason to avoid the simple divide-and-conquer solution. Consider the Towers of Hanoi problem, which is presented in Exercise 17. Briefly, the problem involves moving n disks from one peg to another given certain restrictions on how they may be moved. In the exercises you will show that the sequence of moves, obtained from the standard divide-and-conquer algorithm for the problem, is exponential in terms of n and that it is the most efficient sequence of moves given the problem\'s restrictions. Therefore, the problem requires an exponentially large number of moves in terms of n

Solution

algorithm factorial( start, end ):

if( start == end ):

return start;

mid = start + ( end- start)/2;

return   factorial( start,mid )*factorial(mid+1, end);

nFactorial = factorial(1,n);

Input size is defined by n= (end-start+1)

No, the time complexity is O(n)

T(n) = 2*T(n/2)    ==> Let n = 2^k,   T(n) = 2²*T(n/4) = 2^kT(1) = nT(1) = O(n)

An instance of size n is divided into two instance of each almost of size n/2. Thus not violating the given conditions