Write an iterative function to compute 2^n, given n greaterthanorequalto 1. What
ID: 3793067 • Letter: W
Question
Write an iterative function to compute 2^n, given n greaterthanorequalto 1. What is the time complexity of this function? Consider the following function int foo(int n) {if (n == 1) return 2; int a = foo(n/2); return a * a;} and int bar(int n) {if (n == 1) return 2; return foo(n/2) * foo(n/2);} Explain why these functions always return the same result, given the same input. Explain why bar is less efficient than foo. What is the running time of each of these functions? use the technique shown in class of tracing the algorithm for small inputs, until you find a pattern. Relate input size to running time. In class, we said that foo computes the function f(n) = 2^n correctly for inputs that are powers of 2 (n = 1, 2, 4, 8, ...), but not for the rest because the division by 2 is an integer division. Modify foo to correctly compute f(n) for all n greaterthanorequalto 1.Explanation / Answer
Hi, Please find my answer.
a)
// Iterative function to compute 2^n
int power2(int n){
int pow = 1;
for(int i=1;i<=n; i++)
pow = pow* 2;
return pow;
}
b)
in foo, we are computing :
int a = foo(n/2)
and returning a*a => foo(n/2)*foo(n/2)
in bar, we are computing and returning :
foo(n/2)*foo(n/2)
So, you can see, both function are returning same value
c)
In foo, we are computing : foo(n/2) only one time and multiplying the result of foo(n/2) to get foo(n/2)*foo(n/2)
But in bar, we are computing foo(n/2) twice.
Thats why foo is more efficient than bar
Time complexity of foo: O(logn) => in ecan recursion we are dividing n by n
Time complexity of bar: O(n) => T(n) = 2T(n/2) + 1
d)
int foo(int n)
{
if( n == 0)
return 1;
int a = power(n/2);
if (n%2 == 0)
return a*a;
else
return 2*a*a;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.