Exams › GATE › Engineering Mathematics
Common Data for Questions 74 and 75:
Consider the following 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
- Θ(n) and Θ(n)
- Θ(2ⁿ) and Θ(n)
- Θ(n) and Θ(2ⁿ)
- Θ(2ⁿ) and Θ(2ⁿ)
Correct answer: Θ(2ⁿ) and Θ(n)
Solution
The function f1(n) exhibits exponential growth due to its recursive calls, leading to a time complexity of Θ(2ⁿ). In contrast, f2(n) uses an iterative approach with a linear loop, resulting in a time complexity of Θ(n).
Related GATE Engineering Mathematics questions
- The second-order differential equation in an unknown function u: u(x,y) is defined as ∂²u/∂x² = 2. Assuming g: g(x), f: f(y), and h: h(y), the general solution of the above differential equation is
- Which of the following equations belong/belongs to the class of second-order, linear, homogeneous partial differential equations:
- The solution of the equation x dy/dx + y = 0 passing through the point (1,1) is
- The Laplace transform F(s) of the exponential function, f(t)=e^(at) when t≥0, where a is a constant and (s−a)>0, is
- The Laplace transform of sinh(at) is
- An ordinary differential equation is given below.
(dy/dx)(x ln x) = y
The solution for the above equation is
(Note: K denotes a constant in the options)
⚔️ Practice GATE Engineering Mathematics free + battle 1v1 →