Common Data for Questions 74 and 75: Consider the following C functions: int…
GATE · 2008 · CSModified — slightly modified from the official paper; see the solution
Common Data for Questions 74 and 75: Consider the following C functions:
int f1(int n) { if (n == 0 || n == 1) return n; else 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]; }
The running time of f1(n) and f2(n) are
- A.
θ(n) and θ(n)
- B.
Θ(φⁿ) and Θ(n)
- C.
θ(n) and θ(2n)
- D.
θ(2n) and θ(2n)
Attempted by 79 students.
Sign up free to check your answer
Sign up freeLoading lesson…