Common Data for Questions 74 and 75: Consider the following C functions: int…

PYQ GATE 2008Modified — 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

  1. A.

    θ(n) and θ(n)

  2. B.

    Θ(φⁿ) and Θ(n)

  3. C.

    θ(n) and θ(2n)

  4. D.

    θ(2n) and θ(2n)

Attempted by 90 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…