Functions
Question 1 
Consider the following C program:
#include <stdio.h> int jumble (int x, int y) { x = 2 * x + y ; return x ; } int main ( ) { int x=2, y=5 ; y = jumble (y, x) ; x = jumble (y, x) ; printf ("%d \n", x) ; return 0 ; }
The value printed by the program is ______.
26  
67  
25  
13 
#include
int jumble(int x, int y)
{
printf("Inside jumble : 2*%d + %d\n", x,y);
x = 2*x +y;
return x;
}
int main()
{
int x=2, y=5;
printf("Initial x=%d, y=%d\n",x,y);
printf("1st jumble call : jumble(%d,%d)\n",y,x);
y = jumble(y,x);
printf("Value of y after 1st jumble = %d\n", y);
printf("2^{nd} jumble call: jumble(%d,%d)\n", y,x);
x = jumble(y,x);
printf("Value of x after 2nd jumble = %d\n", x);
printf("Final : %d\n", x);
return 0;
}
////////////////////////////////////OUTPUT
Initial x=2, y=5
1^{st} jumble call: jumble(5,2)
Inside jumble : 2*5 + 2
Value of y after 1^{st} jumble = 12
2^{nd} jumble call: jumble(12,2)
Inside jumble : 2*12 + 2
Value of x after 2nd jumble = 26
Final : 26
Question 2 
Consider the following C function.
void convert (int n) { if (n < 0) printf ("%d", n); else { convert (n/2); printf ("%d", n%2); } }
Which one of the following will happen when the function convert is called with any positive integer n as argument?
It will print the binary representation of n in the reverse order and terminate.  
It will not print anything and will not terminate.  
It will print the binary representation of n and terminate.  
It will print the binary representation of n but will not terminate. 
Sequence of function calls
Convert(6)
Convert(3)
Convert(1)
Convert(0)
:
Convert(0)
:
:
It will not terminate and never produce any output.
Note:
There is no instruction which stops the loop.
Question 3 
How many onto (or surjective) functions are there from an nelement (n ≥ 2) set to a 2element set?
2^{n}  
2^{n}1  
2^{n}2  
2(2^{n}– 2) 
Onto function is possible if m ≥ n. So, no. of onto functions possible is,
n^{m}  ^{n}C_{1} (n1)^{m} + ^{n}C_{2} (n2)^{m} + .......
Here in Question,
m = n, n = 2
So, the final answer will be,
= 2^{n}  ^{2}C_{1} (21)^{n} + ^{2}C_{2} (22)^{n}
= 2^{n}  2 × 1 + 0
= 2^{n}  2
Question 4 
Let A be a set of n(>0) elements. Let N_{r} be the number of binary relations on A and let N_{f} be the number of functions from A to A.
 (a) Give the expression for N_{r} in terms of n.
(b) Give the expression for N_{f} in terms of n.
(c) Which is larger for all possible n, N_{r} or N_{f}?
Theory Explanation is given below. 
Question 5 
On the set N of nonnegative integers, the binary operation __________ is associative and noncommutative.
fog 
(fog)(x) = f(g(x))
It is associative, (fog)oh = fo(goh), but its usually not commutative. fog is usually not equal to gof.
Note that if fog exists then gof might not even exists.
Question 6 
Consider the following C functions.
int fun1 (int n) { int fun2 (int n) { static int i = 0; static int i = 0; if (n > 0) { if (n > 0) { ++i; i = i + fun1 (n); fun1 (n1); fun2 (n1); } } return (i); return (i); } }
The return value of fun2 (5) is _______.
55 
int fun1(int n) {
printf("fun1 call\n");
static int i = 0;
if(n>0){
++i;
printf("fun1(%d1)\n",n);
fun1(n1);
}
printf("fun1(%d)= %d\n",n, i);
return(i);
}
int fun2(int n) {
printf("\n******* fun2 call ********\n");
static int i = 0;
if(n>0){
printf("%d + fun1(%d)\n", i,n);
i=i+fun1(n);
fun2(n1);
}
printf("fun2(%d)= %d\n",n, i);
return(i);
}
void main()
{
printf("final = %d\n", fun2(5));
}
Check step by step hand run of the code to understand the recursion:
******* fun2 call ********
0 + fun1(5)
fun1 call
fun1(51)
fun1 call
fun1(41)
fun1 call
fun1(31)
fun1 call
fun1(21)
fun1 call
fun1(11)
fun1 call
fun1(0)= 5
fun1(1)= 5
fun1(2)= 5
fun1(3)= 5
fun1(4)= 5
fun1(5)= 5
******* fun2 call ********
5 + fun1(4)
fun1 call
fun1(41)
fun1 call
fun1(31)
fun1 call
fun1(21)
fun1 call
fun1(11)
fun1 call
fun1(0)= 9
fun1(1)= 9
fun1(2)= 9
fun1(3)= 9
fun1(4)= 9
******* fun2 call ********
14 + fun1(3)
fun1 call
fun1(31)
fun1 call
fun1(21)
fun1 call
fun1(11)
fun1 call
fun1(0)= 12
fun1(1)= 12
fun1(2)= 12
fun1(3)= 12
******* fun2 call ********
26 + fun1(2)
fun1 call
fun1(21)
fun1 call
fun1(11)
fun1 call
fun1(0)= 14
fun1(1)= 14
fun1(2)= 14
******* fun2 call ********
40 + fun1(1)
fun1 call
fun1(11)
fun1 call
fun1(0)= 15
fun1(1)= 15
******* fun2 call ********
fun2(0)= 55
fun2(1)= 55
fun2(2)= 55
fun2(3)= 55
fun2(4)= 55
fun2(5)= 55
final = 55
Question 7 
int tob (int b, int* arr) {
int i;
for (i=0; b>0; i++) {
if (b%2) arr [i] = 1;
else arr [i] = 0;
b = b/2;
}
return (i);
}
int pp (int a, int b) {
int arr [20];
int i, tot = 1, ex, len;
ex = a;
len = tob (b,arr);
for (i=0; i
tot = tot * ex;
ex = ex * ex;
}
return (tot);
}
The value returned by pp(3,4) is ________.
81 
a=3,b=4
tot=1
ex=a=3
len=tob(b,arr) which is 3
[
tob(4,arr)==>
b=4
b%2 =4%2=0 Condition is false then arr[0]=0
=> b=b/2 =4/2 =2
b=2
b%2 =2%2=0 condition is false then arr[1]=0
=>b=b/2=2/2=1
b=1
then b%2=1%2 condition is true then arr[2]=1
=>b=b/2=1/2=0
The i value is 3 [length is 3]
]
i=0,
arr[0] ==1 condition is false
ex=3*3=9
i=1
arr[1]==1 condition is false
then
ex=9*9=81
i=2
then arr[2]==1 condition is true
tot=tot*ex=1*81=81
ex=81*81
Finally it returns tot value which 81.
Question 8 
The function f(x,y) = x^{2}y  3xy + 2y + x has
no local extremum  
one local minimum but no local maximum  
one local maximum but no local minimum  
one local minimum and one local maximum 
Question 9 
The Laplace transform of the periodic function f(t) described by the curve below, i.e.,
is _________
Out of syllabus. 
Question 10 
Let A and B be sets with cardinalities m and n respectively. The number of oneone mappings (injections) from A to B, when m < n, is:
m^{n}  
^{n}P_{m}  
^{m}C_{n}  
^{n}C_{m}  
^{m}P_{n} 
A = {a_{1}, a_{2}, ... a_{m}} and
B = {b_{1}, b_{2}, ... b_{n}}
A oneone function 'f' assigns each element a_{i} of A a distinct element, b_{j}=f(a_{i}) of B_{i} for a, there are n choices, for a_{2} there are n1 choices, for a_{m} there are (n(m1)) choices.
i.e.,
Question 11 
1441  
3443  
12344321  
43211234 
demo(123)> It will print “3” then 3!=10 condition is true again it call demo(12)
demo(12)> It will print “2” then 2!=10 condition is true again it call demo(1)
demo(1)> It will print “1” then 1!=10 condition is true again it call demo(0)
It will print again 1,2,3 and 4 as there is another Print statement is in each function call.
Question 12 
910  
920  
870  
900 
Step2: We pass address of number as parameters in the square function. As per the concept of function overloading in C++ the second square function will be executed.
Step3: (*y) will be executed first since decrement operator has the higher precedence than multiplication.
*x = (*x) * (*y);
*x = 30 * 29;
*x = 870
Note: x is a pointer variable and it holds the address of the variable number.
Question 13 
Call swap (a, b)  
Call swap (&a, &b)  
swap(a, b) cannot be used as it does not return any value  
swap(a, b) cannot be used as the parameters passed by value 
Question 14 
20 10 10  
20 10 20  
20 20 20  
10 10 10 
Step2: By default tmp value 20 will print initially.
Step3: It calls fun() then it will print 10
Step4: Again we are in main() function and printing value 20. Actually, the static value will return because its scope is a lifetime. But we are given tmp value as global. So, it prints 20 instead of 10.
Question 15 
y(0) = 1,
y(1) = 0,
y(2) = 1,
y(3) = 10 is
x3 +2 x2 + 1  
x3 + 3x2 + 1  
x3 + 1  
x3 – 2 x2 + 1 
x = 0: y(x) = 1
x = 1: y(x) = 0
x = 2: y(x) = 8  8 + 1 = 1
x = 3: y(x) = 27  18 + 1 = 10
Question 16 
3  
4  
6  
9 
=a_{0}+X(a_{1}+X(a_{2}+a_{3}X))
↓ ↓ ↓
③ ② ①
Here, minimum 3 multiplication needed
Question 17 
E1  
E  
1 – E^{1}  
1 – E 
Question 18 
f (x_{0}) > 0  
f (x_{0}) f (x_{0})” > 0  
f (x_{0}) f (x_{0})” < 0  
f (x_{0})” > 0 
Question 19 
15  
7  
11  
3 
Substitute all the value of x from 0 to 5
The value of f(x) is 3 when x=0
The value of f(x) is 9 when x=1
The value of f(x) is 11 when x=2
The value of f(x) is 9 when x=3
The value of f(x) is 3 when x=4
The value of f(x) is 7 when x=5
so the least value is 11
Second method:
→We can solve this one by using derivatives.
→Given function is f(x) = 2x^{2} 8x 3
→ f'(x)=4x8 (first derivative)
a f''(x)=4 (Second derivative)
Here we got constant value which means that it has minimal value at the point x=2
So we can find the minimum value by substituting value 2 in place of “x” in the given function.
Minimum value is 2⨉(2)^{2} 8⨉(2) 3= 11
Question 20 
Given below are three implementations of the swap( ) function in C++ :
Which of these would actually swap the contents of the two integer variables p and q ?
(a) only  
(b) only  
(c) only  
(b) and (c) only

Module  (b) is call by reference. So, the modification of content in the function reflects the changes in the main program. Swapping is done in the module  (b).
Module  (c) is passing addresses as parameters but in the functions definition. We are changing the addresses not the content. So, swapping of the values can’t be done.
Question 21 
Switch  
Go to  
go back  
Retun 
● The execution resumes in the calling function at a point immediately following the call.
Question 22 
void greet (int n)
{
if (n>0)
{
printf("hello");
greet(n1);
}
printf("world");
}
If you run greet(n) for some nonnegative integer n, what would it print?
n times “hello”, followed by n + 1 times “world”  
n times “hello”, followed by n times “world”  
n times “helloworld”  
n + 1 times “helloworld”  
n times “helloworld”, followed by “world” 
Question 23 
#include
void dynamic(int s,..)
{
printf("%d",s);
}
int main()
{
dynamic(2,4,6,8);
dynamic(3,6,9);
return 0;
}
23  
compile error  
43  
32 
● Old compiler may support that syntax, in that syntax only first argument is defined which consists of remainings arguments but not defined.
● For the function call dynamic(2,4,6,8), first argument 2 is printed.
● For the function call dynamic(3,6,9);first argument 3 is printed.
Question 24 
main()
{
inc();
inc();
inc();
}
inc()
{
static int x;
printf("%d", ++x);
}
prints 012  
prints 123  
prints 3 consecutive, but unpredictable numbers  
prints 111 
Static storage class by default value is 0.
Step1: We are calling inc( ) in main function. So, it will enter into inc() function.
Here, we are using pre increment function, so it replaced 0 with 1.
Step2: Second inc() in main function. So, it will enter into inc() function.
Here, we are using pre increment function, so it replaced 1 with 2.
Step3: Third inc() in main function. So, it will enter into inc() function.
Here, we are using pre increment function, so it replaced 2 with 3.
Note: The static storage class instructs the compiler to keep a local variable in existence during the lifetime of the program instead of creating and destroying it each time it comes into and goes out of scope.
Question 25 
In C language ______ is a process in which a function calls itself repeatedly until some specified condition has been satisfied
Infinite loop
 
Call by value
 
Call by reference
 
Recursion 
Question 26 
the class of which it is member  
the object of which it is member  
the public part of its class  
the private part of its class 
→ Functions within classes can access and modify (unless the function is constant) data members without declaring them, because the data members are already declared in the class.
Question 27 
Class templates and function templates are instantiated in the same way  
Class templates differ from function templates in the way they are initiated  
Class template is initiated by defining an object using the template argument  
Class templates are generally used for storage classes  
None of the above 
(2) FALSE: Class templates differ from function templates in the way they are initiated
(3) FALSE: Class template is initiated by defining an object using the template argument
(4)FALSE: Class templates are generally used for storage classes
Question 28 
Constant  
Structure  
Array  
Header file 
→ Header file is a library file, we can not passed to a function in C++.
→ We can pass constant,Structure and Array
Question 29 
A function can only be declared a friend by a class itself.  
Friend functions are not members of a class, they are associated with it.  
Friend functions are members of a class.  
It can have access to all members of the class, even private ones. 
TRUE: function can only be declared a friend by a class itself.
TRUE: Friend functions are not members of a class, they are associated with it.
FALSE:Friend functions are members of a class.
TRUE: It can have access to all members of the class, even private ones.
Question 30 
4  
3  
2  
1 
→ Templates are a feature of the C++ programming language that allows functions and classes to operate with generic types. This allows a function or class to work on many different data types without being rewritten for each one.
Question 31 
Overloads  
Friendships  
Inherits  
Overrides 
Question 32 
is an instance of a class for which operator ( ) is a member function.  
is an instance of a class for which operator → is a member function.  
is a pointer to any function  
is a member function of a class 
Question 33 
Serially useable procedures  
Concurrent procedures  
Reentrant procedures  
Top down procedures 
→ The interruption could be caused by an internal action such as a jump or call, or by an external action such as an interrupt or signal. The previous invocations may resume correct execution before the reentered invocation completes, unlike recursion, where the previous invocations may only resume correct execution once the reentered invocation completes.
Rules:
1. Reentrant code may not hold any static or global nonconstant data.
2. Reentrant code may not modify itself.
3. Reentrant code may not call nonreentrant computer programs or routines.
Question 34 
private and public  
public  
public and private  
private 
Question 35 
Serially usable procedure  
Concurrent procedure  
Reentrant procedure  
Top down procedure 
Rules:
1. Reentrant code may not hold any static or global nonconstant data.
2. Reentrant code may not modify itself.
3. Reentrant code may not call nonreentrant computer programs or routines.
Question 36 
are initialized during each execution of the function  
are retained from the last execution  
are maintained in a stack  
are ignored 
Question 37 
x ^{8} – 71 and x ^{8} – 71  
x ^{8} – 73 and x^{8} – 73  
x ^{8} + 71 and x ^{8} + 71  
x ^{8} + 73 and x ^{8} + 73 
for, ho(gof)
gof=g(f(x))
=g(x ^{4} )
=√(x ^{8} +1)
ho(gof)=h(gof)
=h(√(x ^{8} +1))
=(√(x ^{8} +1) 2 +72
=x ^{8} +1+72
=x ^{8} +73
√ x ^{2} + 1 , h(x) = x^{ 2} + 72
for, (hog)of,
hog=h(g(x))
=h(√(x ^{2} +1)
=(√(x ^{2} +1) 2 +72
=x ^{2} + 1+72
=x ^{2} +73
(hog)of=(hog)(f(x))
=(hog)(x ^{4} )
=(x ^{4} ) ^{2} +73
=x ^{8} +73
Hence, optionD is the correct answer
Question 38 
Address of the array  
Values of the elements of the array  
Base address of the array  
Number of elements of the array 
Question 39 
avoid arguments between classes.  
allow access to classes whose source code is unavailable.  
allow one class to access an unrelated class.  
None of the above 
→A function can only be declared a friend by a class itself.
→It can have access to all members of the class, even private ones.
→ A friend function can be used to allow one class to access an unrelated class.
Question 40 
0  
1  
1  
Program do not return a value. 
Question 41 
Which of these would actually swap the contents of the two integer variables p and q ?
(a) only  
(b) only  
(c) only  
(b) and (c) only 
Module (b) is call by reference , So the modification of content in the function reflects the changes in the main program. Swapping is done in the module (b).
Module (c) is passing addresses as parameters but in the functions definition , We are changing the addresses not the content So swapping of the values can’t be done.
Question 42 
(a)(i), (b)(ii), (c)(iii)  
(a)(iii), (b)(ii), (c)(i)  
(a)(ii), (b)(i), (c)(iii)  
(a) (ii), (b)(iii), (c)(i) 
∀ x, x ′ ∈ X , f (x) = f (x ′ ) ⇒ x = x ′
Or, equivalently (using logical transposition),
∀ x, x ′ ∈ X , x = / x ′ ⇒ f (x) = / f (x ′ )
● The function is surjective (onto) if each element of the codomain is mapped to by at least one element of the domain. (That is, the image and the codomain of the function are equal.) A surjective function is a surjection. Notationally:
∀ y ∈ Y , ∃x ∈ X such that y = f (x)
A constant function is a function whose (output) value is the same for every input value. For example, the function y(x) =4 is a constant function because the value y(x) is 4 regardless of the input value x
Question 43 
Diagonalization  
Communitivity  
Mathematical Induction  
Matrix Multiplication 
→ Mathematical Induction is a special way of proving things. It has only 2 steps:
Step1: Show it is TRUE for the first one
Step2: Show that if any one is TRUE then the next one is true
Then all are true
Question 44 
find (int x, int y)
{return ((x < y) ? 0 : (x  y)) ; }
Let a, b be two nonnegative integers. The call find {a, find(a, b)} can be used to find the
maximum of a, b  
positive difference of a, b  
sum of a, b  
minimum of a, b 
Question 45 
zero  
2  
2  
any number 
Question 46 
Descriptive Explanation 
Clearly mystery(1, 0) = mystery(0, 1) = 1 + 1 = 2 = 0 + 2. Assuming that mystery(1, n − 1) = n + 1, mystery(1, n) = mystery(0, mystery(1, n − 1)) = mystery(0, n + 1) = (n + 1) + 1 = n + 2.
(ii) mystery(2, n) = 2n + 3, and we again prove this by induction on n.
Clearly mystery(2, 0) = mystery(1, 1) = 1 + 2 = 3 = 2 · 0 + 3. Assuming that
mystery(2, n−1) = 2(n−1)+3 = 2n+1, mystery(2, n) = mystery(1, mystery(2, n−1)) = mystery(1, 2n + 1) = (2n + 1) + 2 = 2n + 3.
(iii) mystery(3, 0) = mystery(2, 1) = 2 + 3 = 5.
mystery(3, 1) = mystery(2, mystery(3, 0)) = mystery(2, 5) = 2 · 5 + 3 = 13.
mystery(3, 2) = mystery(2, mystery(3, 1)) = mystery(2, 13) = 2 · 13 + 3 = 29.
mystery(3, 3) = mystery(2, mystery(3, 2)) = mystery(2, 29) = 2 · 29 + 3 = 61.
Question 47 
Descriptive Explanation 
We first prove by induction on the number of digits in m that the result of f (m, n) is the reverse of m appended to n.
• If m = 0, then f (m, n) = n, as we require.
• If m < 10, then q = 0 and r = m, and a recursive call is made to f (0, 10n + m) = 10n + m, which is the reverse of the digits of m appended to n.
• If m > 10, then r is the last digit of m, and q is all the other digits. There is a recursive call to f (q, 10n + r), whose output (by induction hypothesis applied on q, which has one fewer digit than m) is the reverse of q appended to 10n + r, which is exactly the reverse of m appended to n.
Now f (a, 0) is the reverse of a, and f (f (a, 0), b) is the reverse of reverse of a appended to b, or in other words, a appended to b. Thus g(m, 1) appends to the last digit of m the other digits of m—performing a right rotate of m, in other words. g(m, n) is just n right rotates performed on m.
It follows that g(3, 7) = 3, g(345, 1) = 534 and g(345, 0) = 345.
It is also easy to see from the code that f (m, n) takes O(log m) time and g(m, n) takes O(n · log m) time.
Question 48 
log _{d} n if d < 0, n_{ d} if d > 0.  
n _{d} for all values of d.  
n × d if d > 0, n ÷ d if d < 0.  
n × d for all values of d. 
Question 49 
2  
1  
2  
4 
Question 50 
Descriptive Explanation 
(b) The worst case complexity is O(n ^{2} ) because of the fixed choice of pivot, as in quicksort.
(c) A typical worst case input would be, for instance, where A is in ascending order and k = n.
Question 51 
k == ij.  
k == ji.  
k == ji.  
Depends on start and end. 
Question 52 
Explanation 
(b) The following is a simple algorithm for computing M . It just compares n with 100, and either subtracts 10 from n or returns a constant, all of which are constant time operations.
if (n> 100) return (n10) else return 91
To prove that the algorithm is correct, we need to show that M (n) = 91 for n < 101. Notice first that M (101) = 91. From the following claim, it follows that M (n) = 91 for all n ≤ 100
Claim: For all k ≥ 1 and all n such that 101 − 11k ≤ n < 101 − 11(k − 1), M (n) = 91.
The proof of the claim is by induction on k.
Suppose k = 1 and 90 ≤ n < 101.
M (n)
= M (M (n + 11))
= M (n + 11 − 10) ( since n + 11 ≥ 101)
= M (n + 1)
Therefore, M (90) = M (91) = · · · = M (100) = M (101) = 91.
Assume the claim holds for k ≤ m. Consider n such that 101 − 11k ≤ n < 101 − 11(k − 1) for k = m + 1.
M (n) = M (M (n + 11))
= M (91) (M (n + 11) = 91, by IH )
= 91 by base case
Thus the claim holds for all k, and hence M (n) = 91 for all n < 101.
Question 53 
Either 1 or 94  
Either 94 or 47  
Either 1 or 47  
None of these 
Question 54 
Explanation 
A(m, n, 1) = A(m, A(m, n − 1, 1), 0) = A(m, m(n − 1), 0) = m + m(n − 1) = mn.
(b) Evaluating A(m, n, 2) for small values of n suggests that A(m, n, 2) = m ^{n} . We verify it using induction. The base case is clear: A(m, 0, 2) = 1 = m ^{0} . For the induction step, assuming that A(m, n − 1, 2) = m ^{n−1} , we have
A(m, n, 2) = A(m, A(m, n − 1, 2), 1) = A(m, m ^{n−1} , 1) = m · m ^{n−1} = m^{ n}.
(c) A(2, 0, 3) = 2.
A(2, 1, 3) = A(2, A(2, 0, 3), 2) = A(2, 2, 2) = 2 ^{2} = 4. A(2, 2, 3) = A(2, A(2, 1, 3), 2) = A(2, 4, 2) = 2^{ 4} = 16. A(2, 3, 3) = A(2, A(2, 2, 3), 2) = A(2, 16, 2) = 2 ^{16} = 65536.
Question 55 
unsigned int f(unsigned int n)
{
unsigned int b=0;
while(n)
{
b+=n&1;
n>>=1;
}
return b;
}
The function f() returns the int that represents the___p___in the binary representation of positive integer n, where P is
number of 0's  
number of bits  
number of consecutive 1's  
number of 1's 
when b += n & 1 is given
n and 1, both will be converted to binary and binary & operation is calculated
any number & 000000001
it will only compare the last bit of both numbers, if both right most bit is 1 then the value is incremented by 1 and the number n is right shifted that means it loses the value of right most bit and again new right most bit is binary anded with 1.
So the value is nothing but the number of 1's of the binary format of number.
Question 56 
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 )?
9  
8  
5  
2 
Condition: n>0
Sum of bits=2 if they given 513. It represented in binary.
Question 57 
Integer procedure P(X,Y);
Integer X,Y;
value x;
Begin
K=5;
L=8
P=x+y;
End
X is called by value and Y is called by name. If the procedure were invoked by the following program fragment
K=0
L=0
Z=P(K,L);
then the value Z would be set equal to
5  
8  
13  
0 
Question 58 
The time complexity of the following C function is (assume n>0)
int recursive (int n) { if (n==1) return(1); else return(recursive (n1) + recursive(n1)); }
O(n)  
O(n log n)  
O(n^{2})  
O(2^{n}) 
Note ‘a’ is a constant O(1) cost that the nonrecursive part of the function takes.
Solving the recurrence by Back Substitution:
T(n) = 2T(n1)+a
T(n1) = 2T(n2)+a
T(n2) = 2T(n3)+a
:
:
Thus we can write the equation as follows
T(n) = 2(2T(n2)+a)+a = 4T(n2) + 2a + a
T(n) = 4(2T(n3)+a) + 2a + a = 8T(n3) + 4a + 2a + a
:
:
:
T(n) = 2^{k} T(nk) + (2^{k}  1)a
On substituting limiting condition,
T(1) = 1
=> n  k = 1
=> k = n1
Therefore, our solution becomes
2^{n1} + (2^{n1}  1)a
= O(2^{n})
Question 59 
int function (int x, int y) { if(y<=0) return x; return function (y, x%y); }
The above recursive function computes ______
GCD of X and Y
 
x^{y}  
y^{x}  
HCF of x and y  
Both A and D 