Bissoy.com
Doctors Medicines MCQs Q&A

Consider the following C code segment int f (int x) { if (x<1) return 1; else return ( f{x-1) + g(x) ); } int g (int x) {  if (x< 2) return 2; else return ( f(x-1) + g(x/2)); } Of the following, which best describes the growth of f(x) as a function of x ?

Consider the following C code segment int f (int x) { if (x<1) return 1; else return ( f{x-1) + g(x) ); } int g (int x) {  if (x< 2) return 2; else return ( f(x-1) + g(x/2)); } Of the following, which best describes the growth of f(x) as a function of x ? Correct Answer Exponential

Explanation

f(n) = f(n-1) + g(n)           ----> 1
g(n) = f(n-1) + g(n/2)       ----> 2

Putting the value of g(n) in equation 1,
f(n) = 2×f(n-1) + g(n) + g(n/2)

So, we can derive the below equation,(by approximation)
f(n) > 2f(n-1)
=> f(n) > 2×2 × f(n-2) ---- because f(n) > 2×f(n-1), so, f(n-1) > 2×2×f(n-2).... so on
=> f(n) > (2n) × f(1) --- here \'^\' denotes the exponent.
So, f(n) > θ(2n)

So, exponential growth for f(x).

correct answer is option 2

Related Questions

What is the output of following program? abstract class Sum { public abstract int sumOfTwo(int n1, int n2); public abstract int sumOfThree(int n1, int n2, int n3); public void disp( ){ System.out.println("Method of class Sum"); } } class DemoAbstract1 extends Sum { public int sumOfTwo(int num1, int num2) { return num1+num2; } public int sumOfThree(int num1, int num2, int num3) { return num1+num2+num3; } public static void main(String args[ ]){ Sum obj = new DemoAbstract1( ); System.out.println(obj.sumOfTwo(3, 7)); System.out.println(obj.sumOfThree(4, 3, 19)); obj.disp( ); } }
What will be the final values of i and j in the following C code?
#include int x = 0;int f(){ if (x == 0) return x + 1; else return x - 1;}int g(){ return x++;}int main(){ int i = (f() + g()) | g(); //bitwise or int j = g() | (f() + g()); //bitwise or}
What will be the final values of i and j in the following C code?
#include int x = 0;int f(){ if (x == 0) return x + 1; else return x - 1;}int g(){ return x++;}int main(){ int i = (f() + g()) || g(); int j = g() || (f() + g());}
Segment CD is shorter than Segment MN, Segment MN is shorter than Segment TR, Segment AB is shorter than Segment CD and Segment MN is shorter than Segment PQ. Which segment is the shortest?
Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order int ProcessArray(int *listA, int x, int n) { int i, j, k; i = 0; j = n-1; do {                k = (i+j)/2;                if (x <= listA[k])                 j = k-1;                 if (listA[k] <= x)                 i = k+1;        } while (i <= j); if (listA[k] == x)                 return(k); else                 return -1; } Which one of the following statements about the function ProcessArray is CORRECT?
Consider the following two C code segment. Y and X are one- and two-dimensional arrays of size n and n × n respectively, where 2 ≤ n ≤ 10. Assume that in both code segments, elements of y are initialized to 0 and each element X[i] [j] of array X is initialized to i + j. Further assume that when stored in main memory all elements of x are in same main memory page frame. Code segment 1:                 //initialize elements of y to 0                 //initialize elements X[i] [j] of X to i+j                       for (i = 0; i < n; i++)                                 Y[i] += X[0] [i]; Code Segment 2:                 //initialize elements of Y to 0                 //initialize elements X[i] [j] of X to i+j                        for (i = 0; i < n; i++)                                 Y[i] += X[i] [0]; Which of the following statements is/are correct? S1: Final contents of array Y will be same in both code segments S2: Elements of array X accessed inside the for loop shown in code segment 1 are contiguous in main memory S3: Elements of array X accessed inside the for loop shown in code segment 2 are contiguous in main memory
The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height(root) to compute the height of a binary tree rooted at the tree pointer root. int height (treeptr n) { if (n == NULL) return -1;   if (n →  left == NULL)        if (n →  right == NULL) return 0;        else return ; \(\boxed{B1}\);     // Box 1 else { h1 = height (n →  left);          if (n → right == NULL) return (1+h1);          else { h2 = height (n → right);          return ; \(\boxed{B2}\)   // Box 2                        }            } } The appropriate expressions for the two boxes B1 and B2 are
Consider the following C function in which size is the number of elements in the array E: int MyX(int *E, unsigned int size) {       int Y = 0;       int Z;       int i, j, k;       for(i = 0; i < size; i++) Y = Y + E[i];       for(i = 0; i < size; i++) for(j = i; j < size; j++) {       Z = 0;       for(k = i; k <= j; k++) Z = Z + E[k];       if (Z > Y) Y = Z; }       return Y; } The value returned by the function MyX is the
Consider the following recursive C function that takes two arguments unsigned int rer (unsigned int n, unsigned int r) { if (n > 0) return (n%r + rer (n/r, r)); else return 0; } What is the return value of the function rer when it is called as rer (513, 2)?
What is the output of this program ? #include
using namespace std;
int n(char, int);
int (*p) (char, int) = n;
int main()
{
(*p)('d', 9);
p(10, 9);
return 0;
}
int n(char c, int i)
{
cout << c << i;
return 0;
}