NEW
Font size
WorksheetsAnalysis of Algorithms
Total questions: 10
Worksheet time: 33mins
What does it mean when we say that an algorithm X is asymptotically more efficient than Y?
X will be a better choice for all inputs
X will be a better choice for all inputs except possibly small inputs
X will be a better choice for all inputs except possibly large inputs
Y will be a better choice for small inputs
Which of the following is not O(n^2)?
(15^10) * n + 12099
n^1.98
n^3 / (sqrt(n))
(2^20) * n
Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4?
f1(n) = 2^n
f2(n) = n^(3/2)
f3(n) = nLogn
f4(n) = n^(Logn)
f3, f2, f4, f1
f3, f2, f1, f4
f2, f3, f1, f4
f2, f3, f4, f1
Consider the following functions:
f(n) = 2^n
g(n) = n!
h(n) = n^logn
Which of the following statements about the asymptotic behavior of f(n), g(n), and h(n) is true?
f(n) = O(g(n)); g(n) = O(h(n))
f(n) = omega (g(n)); g(n) = O(h(n))
g(n) = O(f(n)); h(n) = O(f(n))
h(n) = O(f(n)); g(n) = omega (f(n))
Which of the following is not true about comparison based sorting algorithms?
The minimum possible time complexity of a comparison based sorting algorithm is O(nLogn) for a random input array
Radix Sort is taken linear time for sorting
Counting Sort is not a comparison based sorting algortihm
Heap Sort is not a comparison based sorting algorithm.
What is time complexity of fun()?
int fun(int n)
{ int count = 0;
for (int i = n; i > 0; i /= 2)
{ for (int j = 0; j < i; j++)
{ count += 1; }}
return count; }
O(n^2)
O(nLogn)
O(n)
O(nLognLogn)
Consider the above functions
Which of the following is true?
(a) h(n) is 0(f(n))
(b) h(n) is 0(g(n))
(c) g(n) is not 0(f(n))
(d) f(n) is 0(g(n))
a
b
c
d
What is the time complexity of fun()?
int fun(int n)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = i; j > 0; j--)
count = count + 1;
return count;
}
Theta (n)
Theta (n^2)
Theta (n*Logn)
Theta (nLognLogn)
What is the time complexity of following function fun()? Assume that log(x) returns log value in base 2.
void fun()
{
int i, j;
for (i=1; i<=n; i++)
for (j=1; j<=log(i); j++)
printf("XYZ");
}
Θ(n)
Θ(nLogn)
Θ(n^2)
Θ(n^2(Logn))
The time complexity of the following C function is (assume n > 0)
int recursive (int n) {
if(n == 1)
return (1);
else
return (recursive (n-1) + recursive (n-1));
}
O(n)
O(n log n)
O(n^2)
O(2^n)
