(a) Write the recurrence relation for the running time T(n) of the function f(n) given below....

Transcribed Image Text:

(a) Write the recurrence relation for the running time T(n) of the function f(n) given below. public static int f(int n) { } if (n == 1) return 2; else return f(n/2) + f(n/2) + g(n); public static int g(int n) { int sum = 0; for (int k = 1; k 1 Where a and b are constants. Solve the recurrence relation by iteration and then determine the big-O complexity of the algorithm. Assume that n is a multiple of 2, i.e., n = 2k You may find the following summation formulae useful: IM- n(n+1) 2 i=1 IM- n(n+1)(2n+1) 6 i=0 12 k 1 x-1 = 2 = 2k-1 1-0 x-1 if x 1 (a) Write the recurrence relation for the running time T(n) of the function f(n) given below. public static int f(int n) { } if (n == 1) return 2; else return f(n/2) + f(n/2) + g(n); public static int g(int n) { int sum = 0; for (int k = 1; k 1 Where a and b are constants. Solve the recurrence relation by iteration and then determine the big-O complexity of the algorithm. Assume that n is a multiple of 2, i.e., n = 2k You may find the following summation formulae useful: IM- n(n+1) 2 i=1 IM- n(n+1)(2n+1) 6 i=0 12 k 1 x-1 = 2 = 2k-1 1-0 x-1 if x 1