1 Crore+ students have signed up on EduRev. Have you? Download the App 
Which of the following is TRUE?
The two numbers given below are multiplied using the Booth's algorithm.
Multiplicand : 0101 1010 1110 1110
Multiplier: 0111 0111 1011 1101
How many additions/Subtractions are required for the multiplication of the above two numbers?
If we use Radix Sort to sort n integers in the range (n^{k/2},n^{k}], for some k>0 which is independent of n, the time taken would be?
The auxiliary space of insertion sort is O(1), what does O(1) mean?
What is the value of following recurrence.
T(n) = T(n/4) + T(n/2) + cn^2
T(1) = c
T(0) = 0
Q. Where c is a positive constant
What is the value of following recurrence. T(n) = 5T(n/5) + , T(1) = 1, T(0) = 0
What is the worst case time complexity of following implementation of subset sum problem.
// Returns true if there is a subset of set[] with sun equal to given sum
bool isSubsetSum(int set[], int n, int sum)
{
// Base Cases
if (sum == 0)
return true;
if (n == 0 && sum != 0)
return false;
// If last element is greater than sum, then ignore it
if (set[n1] > sum)
return isSubsetSum(set, n1, sum);
/* else, check if sum can be obtained by any of the following
(a) including the last element
(b) excluding the last element */
return isSubsetSum(set, n1, sum) 
isSubsetSum(set, n1, sumset[n1]);
}
Suppose T(n) = 2T(n/2) + n, T(0) = T(1) = 1 Which one of the following is false.
a) T(n) = O(n^2)
b) T(n) = θ(nLogn)
c) T(n) = Ω(n^2)
d) T(n) = O(nLogn)
Consider the following recurrence:
Q. Which one of the following is true?
The running time of an algorithm is represented by the following recurrence relation:
Q. Which one of the following represents the time complexity of the algorithm?
The running time of the following algorithm
is best described by
What is the time complexity of the following recursive function:
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));
}
Consider the following recurrence T(n) = 3T(n/5) + lgn * lgn What is the value of T(n)?
Consider the following recurrence.
Q. What is the value of recurrence?
Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?
T(n) = 2T(n/2) + Logn
Consider the following recurrence relation
The value of T(m^{2}) for m ≥ 1 is
The solution to the recurrence equation T(2^{k}) = 3 T(2^{k1}) + 1, T (1) = 1, is:
Select the correct asymptotic complexity of an algorithm with runtime T(n, n) where
T(x, c) = Θ(x) for c <= 2,
T(c, y) = Θ(y) for c <= 2, and
T(x, y) = Θ(x+y) + T(x/2, y/2)
Let f(n) = n and g(n) = n^{(1+sin n)}, where n is a positive integer. Which of the following statements is/are correct?
I. f(n) = O(g(n))
II. f(n) = Ω(g(n))
151 docs216 tests

151 docs216 tests
