Test: Time Complexity- 1 - Computer Science Engineering (CSE) MCQ
10 Questions MCQ Test - Test: Time Complexity- 1
The below question is based on following program:
procedure mystery (A : array [1..100] of int)
int i,j,position,tmp;
begin
for j := 1 to 100 do
position := j;
for i := j to 100 do
if (A[i] > A[position]) then
position := i;
endfor
tmp := A[j];
A[j] := A[position];
A[position] := tmp;
endfor
end
The number of times the test 
is executed is:
is executed is:How many times is the comparison i > = n performed in the following program?
int i=85, n=5;
main() {
while (i >= n) {
i=i-1;
n=n+1;
}
}
}
| 1 Crore+ students have signed up on EduRev. Have you? Download the App |
Suppose we want to arrange the numbers stored in any array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case is
If n is a power of 2, then the minimum number of multiplications needed to compute an is
Let S be a sorted array of n integers. Let T(n) denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than 1000 in S. Which of the following statement is true?
The cube root of a natural number n is defined as the largest natural number m such that 
The complexity of computing the cube root of n (n is represented by binary notation) is
This check takes 
time and in the worst case we need to do the search 
So, options (A) and (B) are wrong.Two matrices M1 and M2 are to be stored in arrays A and B respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to compute M1*M2 will be
Let A[1, …n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time complexity is θ(m). Consider the following program fragment written in a C like language:
counter = 0;
for (i=1; i<=n; i++)
{ if a[i] == 1) counter++;
else {f (counter);
counter = 0;}
}
The complexity of this program fragment is
for all i,and then the loop executes with time complexity θ(1) for each iteration and hence overall time complexity of θ(n) and we can say time complexity of the code fragment is Ω(n) and hence options a and b are false.
is called. But due to Counter =0after each call to f(), we have, 
we can say it is θ(n) Option (C). (Option D is false because the small o
as in worst case we can have equal number of 0's and 1's in array a giving time complexity 
Consider the following C-program fragment in which i, j and n are integer variables.
for( i = n, j = 0; i > 0; i /= 2, j +=i );
Let val ( j ) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?
Top Courses for Computer Science Engineering (CSE)
Important Questions for Time Complexity- 1
Time Complexity- 1 MCQs with Answers
Online Tests for Time Complexity- 1
|
© EduRev
|
Education Revolution
|
|
