Given these methods:
METHOD math1:
public int math1( int n ) {
if (n <= 1) {
return 1;
} // if
else {
return ( n * 2 ) + math1( n-1 );
} // else
} // math1
METHOD math2:
public int math2( int n ) {
if (n <= 1) {
return 1;
} // if
else {
return n + math1( n ) * math2( n/2 );
} // else
} // math2
(a) Set up a recurrence relation for the running time of the method math1 as a function of n. Solve your recurrence relation to specify theta bound of math1.
(b) Now set up a recurrence relation for the running time of the method math 2 as a function of n. Solve your recurrence relation to specify the Big-Oh bound of math 2.
HINT: When doing this, the call to math 1 can be replaced by the equation that you found when solving the recurrence relation for math 1 in part a).
Given these methods: METHOD math1: public int math1( int n ) { if (n <= 1) { return 1; } // if...
Consider the following recursive method for finding the maximum element in an int array: public int static max(int[] a, int lo, int hi) { if (lo > hi) return a[lo]; int mid = (lo + hi) / 2; int loMax = max(a, lo, mid); int hiMax = max(a, mid+1, hi); if (loMax > hiMax) return loMax; else return hiMax; } Write down the recurrence relation for counting the number of times the comparison if (loMax > hiMax) is performed. Use...
Compute the recurrence relation, T(n), for the following function, solve it, and give a e bound. Justify your answer public static double myPower(double r, int n) if (n1){ return 1 } else if (n % 2 == 0) { double tmp myPower (r, n/2); return tmp tmp; } else{ myPower (r, (n 1)/2); return }
b) Consider the following code. public static int f(int n) if (n == 1) return 0; else if (n % 2 == 0). return g(n/2); else return g(n+1); public static int g(int n) int r = n % 3; if (r == 0) return f(n/3); else if (r == 1) return f(n+2); else return f(2 * n); // (HERE) public static void main(String[] args) { int x = 3; System.out.println(f(x)); (1) (5 points) Draw the call stack as it would...
3. Consider the mystery method given. public static int mystery ( int n) [ if (n == 0 ) { return 1; How do we get the values for recurse? else if (n%2 == 0 ) { int recurse = mystery ( n - 1); int result = recurse + n; return result; since n =5, we go to the else statement and do int recurse = mystery(5-1) which equals 4? why is 3 written? else { int recurse =...
3) [16 points total] Consider the following algorithm int SillyCalc (int n) int i; int Num, answer; if (n <= 4) return n 10; else { Num-SillyCalcl n/4) answer = Num + Num + 10; for (i-2; i<-n-1; ++) answer- answer+ answer; return answer; Do a worst case analysis of this algorithm, counting additions only (but not loop counter additions) as the basic operation counted, and assuming that n is a power of 2, i.e. that n- 2* for some...
Consider the following method: Linel: public static int mystery(int n) { Line2: if (n < 10) { ine3: return n; Line4: } else { Line5: int a = n/10; Line 6: int b = n % 10; Line 7: return mystery(a + b); Line 8: } Line 9: } What is the result of the following call? System.out.println(mystery(648)); 18 8 12
For each of the following recursive methods available on the class handout, derive a worst-case recurrence relation along with initial condition(s) and solve the relation to analyze the time complexity of the method. The time complexity must be given in a big-O notation. 1. digitSum(int n) - summing the digits of integer: int digitSum(int n) { if (n < 10) return n; return (digitSum(n/10) + n%10); } 2. void reverseA(int l, int r) - reversing array: void...
Q5 (25pts) Consider the code: int foo(int N){ if (N <= 3) return 2; int res1 = 3*foo(N-4); int res2 = foo(N-2); return res1-res2; } a) (6 points) Write the recurrence formula for the time complexity of this function (including the base cases) for N>=0. You do NOT need to solve it. b) (5 points) Draw the tree that shows the function calls performed in order to compute foo(8) (the root will be foo(8) and it will have a child...
Consider the following recursive algorithm for computing the sum of the first n cubes: S(n) = 13 + 23 + … + n3. (a) Set up a recurrence relation for the number of multiplications made by this algorithm. (b) Provide an initial condition for the recurrence relation you develop at the question (a). (c) Solve the recurrence relation of the question (a) and present the time complexity as described at the question number 1. Algorithm S n) Input: A positive...
PROBLEM 1 (24 points): For each of the recursive functions below and on the next page, give a correct recurrence relation expressing its runtime and then a tight runtime bound for the recurrence relation. Functions that take parameters lo and hi: n=hi-lo+1 RECURRENCE RELATION: int foo(int a[], int lo, int hi) { int x, i, j, m; X = 0; if(lo==hi) return a[10]; for(i=lo; i<=hi; i++) { for(j=i+1; j<=hi; j++) { if(a[i] % 2) x += a[i]; else x -=...