1
GATE CSE 2007
MCQ (Single Correct Answer)
+2
-0.6
Consider the following C code segment:
int IsPrime(n){
 int i, n;
 for(i=2; i<=sqrt(n);i++){
  if(n % i == 0){
    printf("No prime\n"); return 0;
  }
  return 1;
 }
}
Let T(n) denote the number of times the for loop is executed by the program on input n. Which of the following is TRUE?
A
T(n) = O ($$\sqrt n $$) and T(n) = $$\Omega \,(\sqrt n )$$
B
T(n) = O ($$\sqrt n $$) and T(n) = $$\Omega \,(1)$$
C
T(n) = O (n) and T(n) = $$\Omega \,(\sqrt n )$$
D
None of the above
2
GATE CSE 2005
MCQ (Single Correct Answer)
+2
-0.6
Consider the following C - function:
double foo(int n){
 int i;
 double sum;
 if(n == 0) return 1.0;
 sum = 0.0;
 for (i = 0; i < n; i++){
  sum += foo(i);
 }
 return sum;
}
Suppose we modify the above function foo() and store the values of foo(i), $$0 \le i \le n$$, as and when they are computed. With this modification, the time complexity for function foo() is significantly reduced. The space complexity of the modified function would be:
A
O(1)
B
O(n)
C
O(n2)
D
O(n!)
3
GATE CSE 2005
MCQ (Single Correct Answer)
+2
-0.6
Consider the following C - function:
double foo(int n){
 int i;
 double sum;
 if(n == 0) return 1.0;
 sum = 0.0;
 for (i = 0; i < n; i++){
  sum += foo(i);
 }
 return sum;
}
The space complexity of the above function is:
A
O(1)
B
O(n)
C
O(n!)
D
O(nn)
4
GATE CSE 2005
MCQ (Single Correct Answer)
+2
-0.6
A Priority-Queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is given below:
10, 8, 5, 3, 2
Two new elements '1' and '7' are inserted in the heap in that order, The level order traversal of the heap after the insertion of the elements is:
A
10, 8, 7, 5, 3, 2, 1
B
10, 8, 7, 2, 3, 1, 5
C
10, 8, 7, 1, 2, 3, 5
D
10, 8, 7, 3, 2, 1, 5
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12