1.Give a useful (big Theta) estimation for each of following function t(n).

a. t(n) is the runtime of following function,

public static int f1(int n){

int mid = n/2;

for (int i = mid; i >= 0; i--) System.out.println(i);

for (int i = mid + 1; i <= n; i++) System.out.println(i); return mid;

}

b. t(n) is the runtime of following function, public static int f2(int n){

if (n < 1) return 1; //update from original int mid = n/2;

mid = f2(mid);

for (int i = 30; i > 0; i /= 3){

System.out.println(i );

}

return mid; }

c. t(n) is the runtime of following function, public static int f3(int n){

for (int i = n; i >= 0; i--){

for (int j = 0, j <= i + i; j++)

for (int k = n; k > 0; k /= 3) System.out.println(i * j + k);

}

return n;

}

d. t(n) is the runtime of following function,

public static int f4(int [] a, int start, int end){

int ans = 0;

if (start >= end) ans = a[start]; else {

int mid = (start + end) / 2;

int x = f4(a, start, mid);

int y = f4(a, mid + 1, end);

print(a, start, end); //print each element in a from start to end if (x < y) ans = x;

else ans = y;

}

return ans;

}

public static void print(int [] a, int s, int e){

for (int i = s; i <= e; i++) System.out.println(i); }

e. t(n) the run time of the following method: The method removeLast for a doubly linked list that has size n