The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

Consider the following functions: F(n) = 2ⁿ
G(n) = n!
H(n) = n^logn
Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

Consider the following C functions:

int f1(int n){
 if(n == 0 || n == 1){
    return n;
 }
 return (2 * f1(n - 1) + 3 * f1(n - 2));
}
int f2(int n){
 int i;
 int X[N], Y[N], Z[N];
 X[0] = Y[0] = Z[0] = 0;
 X[1] = 1; Y[1] = 2; Z[1] = 3;
 for(i = 2; i <= n; i++){
  X[i] = Y[i - 1] + Z[i - 2];
  Y[i] = 2 * X[i];
  Z[i] = 3 * X[i];
 }
 return X[n];
}

f1(8) and f2(8) return the values

You are given the post order traversal, P, of a binary search tree on the n element, 1,2,....,n. You have to determine the unique binary search tree that has P as its post order traversal. What is the time complexity of the most efficient algorithm for doing this?