The problem of finding the multiplication of two variables a

The problem of finding the multiplication of two variables a and b can be solved by addition method. Specifically, a times b is equivalent to adding a for b times. For example, 5 times 4 = 5 + 5 + 5 + 5 = 20 Assuming that parameter b is a non-zero positive integer. Figure Q3 shows the implementations of the multiplication function using both iterative and recursive approaches.//Iterative multiplication function int multiply (int a, int b) int i, result = 0 for (i = b; I > = 1; i--) result = result + a return result;//Recursive multiplication function int multiply 2 (int a, int b) {if (b == 1) return a; else return a + multiply2 (a, b - 1);} Both iterative and recursive functions may have infinite loop. Give one possible reason for infinite recursion and infinite iteration, respectively. Write a program segment to accomplish each of the following tasks: declare an integer variable called result, make an appropriate function call to the function multiply2 to determine the multiplication of 8 and 6, and stores the result of calculation in result, display the result of the calculation on the monitor screen Calculate the worst-case time complexity and estimate the Big-O of the functions multiply l and multiply 2 given in Figure 3. Indicate clearly the time complexity of each statement (if any). Based on your finding in part (c), comment on the efficiency of both implementations in term of execution time.

Solution

a)both the functions do not have infinite loop.

b) #include <stdio.h>

int multiply1(int,int);

int multiply2(int,int);

int main()

{

int result=0;

result = multiply2(8,6);

printf(\"Result is : %d\",result);

}

c)Big-O of multiply1 : O(n)

Big O of multiply2: O(n)

As addition is taking place in both the functions

d)multiply1 is more efficient as recursive function multiply2 have a function call which is more expensive than a jump.Also recursive function eats up more stack space i.e memory.