1. Consider the following recursive function F(int n) int F(int n) { if (n=1) return 1;...

  

Transcribed Image Text:

1. Consider the following recursive function F(int n) int F(int n) { if (n=1) return 1; else { int x = F(n/2)+F(n/2); G(n, x); // assume function G(n, x) is defined } (a) Assume the running time of function G(n, x) is O(1). Setup recurrence for function F(n), then solve the recurrence using the master theorem. (b) Repeat (a) if the running time of G(n, x) is O(n). (c) Repeat (a) if the running time of G(n, x) is O(n). 1. Consider the following recursive function F(int n) int F(int n) { if (n=1) return 1; else { int x = F(n/2)+F(n/2); G(n, x); // assume function G(n, x) is defined } (a) Assume the running time of function G(n, x) is O(1). Setup recurrence for function F(n), then solve the recurrence using the master theorem. (b) Repeat (a) if the running time of G(n, x) is O(n). (c) Repeat (a) if the running time of G(n, x) is O(n).