Question regarding Recurrence function. I've written my answer, please help me to check my answer. If there's something wrong, please explain and correct for me so I can improve the concept.

My answer:

Question 1(a)

(i) Describe what the function compute?

Ans: (assume that n >= 0)

(ii) Give recurrence relation.

Ans:

Base case:

Recursive:

(ii) Solve recurrence to get running time for the function.

Ans:

Question 1(b):

(i) Describe what the function compute?

Ans: (assume that n >= 0)

(ii) Give recurrence relation.

Ans:

Base case:

Recursive:

(ii) Solve recurrence to get running time for the function.

Ans:

Question 1(c):

(i) Describe what the function compute?

Ans:

(ii) Give recurrence relation.

Ans:

Base case:

Recursive:

(ii) Solve recurrence to get running time for the function.

Ans:

Question 1(d):

(i) Describe what the function compute?

Ans:

(ii) Give recurrence relation.

Ans:

Base case: for n

Recursive: for n > 1

(ii) Solve recurrence to get running time for the function.

Ans:

Question 2(a)

To prove bound for follow recurrence relation:

Since we assume that (an element of big theta(n^2))

Proof from base case:

which is not true for all C, so this base case don't holds. Try next:

true if , so base case holds.

Next, we show that :

, is true if

(hence by principle of mathematical induction, proven)

Please let me know if I've did any of the problems wrongly and explain why its wrong so I can learn.

Best Regards.

1. For each of the following recursive functions: (1 point) Describe what the function computes (careful, some of these are tricky!) (1 point) Give a recurrence relation that describes the running time of the function (Give both base and recursive cases) (2 point) Solve the recurrence to get a running time for the function. Use either the repeated substitution method, or the recursion tree method (which is essentially the same as the repeated substitution method, just a little more graphical). Do not use the master method for this question (you will have a chance to use the master method on later questions!) (a) int recursive1(int n) if (n=0) return 0; else 1 recursive1(n-1); (b) int recursive2(int n) if (n== 0) return 1; else recursive2(n-1)recursive2 (n-1); (c) int rui(int n) if (n== 0) return 1; else 2recursive3(n-1) (d) int recursive4(int n) int no op; if (n > 1) for (int i = 0; i