Hello, attached below you will find a simple exercise with the instructions to follow.

Thank you so much in advance!

1.) Give running times for each of the following functions:

(Part- A.)

int func1(int n) { int s = 0; int i = n; while ( i >= 0 ) { int j = n*n; while ( j >= 1) { j = j / 2; s = s + i*j; } i = i - 4; } return s; } 

(Part- B.)

//Note: function func2 calls the function func1 defined in, above, question 1 (Part- A.) int func2(int n) { int res = func1(n*n); if (res > 1000) { for (int k =0; k < n; k++) { res += func1(n); } } return res; }

2.) Consider the following recursive function:

int recursive1(int n) { if (n > 1) { return 2 * recursive1(n-1); } else { return n; } }

(Part- A.) Describe what the function computes

(Part- B.) Give a recurrence relation that describes the running time of this recursive function (give both base and recursive cases)

(Part- C.) Solve the recurrence relation to get running time by using the repeated substitution method