WorksheetsDAA QUIZ-1 FALL SEM(2025-2026)
Total questions: 20
Worksheet time: 20mins
1. Which of the following shows the correct relationship among some of the more common computing times on algorithms
O(log n) < O(n) < O( n* log n) < O(2n ) < O(n2 )
O(n) < O(log n) < O( n* log n) < O(2n ) < O(n2 )
O(n) < O(log n) < O( n* log n) < O(n2 ) < O(2n )
O(log n) < O(n) < O( n* log n) < O(n2 ) < O(2n )
Suppose we have an O(n) time algorithm that finds the median of an unsorted array. Now consider a QuickSort implementation where we first find the median using the above algorithm, then use the median as a pivot. What will be the worst-case time complexity of this modified QuickSort?
O(n^2 Logn
O(n^2)
O(n Logn Logn)
O(nLogn)
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(n2)
O(n*log(n))
O(n)
O(n*log(n*Log(n)))
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 (n2)
Theta (n*log(n))
Theta (n*(log(n*log(n))))
Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3, and f4?
f1(n) = 2n
f2(n) = n(3/2)
f3(n) = n*log(n)
f4(n) = nlog(n)
f3, f2, f4, f1
f3, f2, f1, f4
f2, f3, f1, f4
f2, f3, f4, f1
What is the time complexity of the following recursive function:
int DoSomething (int n)
{
if (n <= 2)
return 1;
else
return (DoSomething (floor(sqrt(n))) + n);
}
Theta(n)
Theta(nlogn)
Theta(logn)
Theta(loglogn)
The time complexity of the following C function is (assume n > 0)
int recursive (mt 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)
Consider the following recurrence T(n) = 3T(n/5) + lgn * lgn What is the value of T(n)?
T(n) = Θ(n^(log53)
T(n) = Θ(n)
T(n) = Θ(n^2)
T(n) = Θ(n^(log5/3))
Which one of the following helps in calculating the longest amount of time taken for the completion of the algorithm?
Theta notation
Big-Oh notation
Omega notation
Time complexity
Which of the following functions provides the maximum asymptotic complexity?
f1(n)=n^(3/2)
f2(n)=n^(logn)
f3(n)=nlogn
f4(n)=2^n
Which of the following functions provides the maximum asymptotic complexity?
T(N)=2T(n/2)+logn
Theta(n)
Theta(n log n)
Theat(n^2)
Theta(logn)
If T(n)=T(n/2) + 1, the time complexity is:
O (log n)
O (n log n)
O(n)
O (1)
Compare growth rates: f(n)=n^2 and g(n)=n^2.logn
f(n)=o (g (n))
g(n)=o (f (n))
f(n)=Theta (g (n))
None
The recurrence T(n)=4T(n/2) + n solves to:
O (n log n)
O(n^2)
O (n^2 log n)
O(log^2 n)
Which of the following is true?
n^log n=o(2^n)
2^n=o(n^ log n)
n^ log n=Theta(2^n)
None
Recurrence T(n)=T(n−1) + n^2 solves to:
O(n)
O(n^2)
O(n^3)
O(2^n)
If an algorithm has worst-case O(n^2) and best-case O(n), its tight bound ThetaΘ can be:
Theta (n^2)
Theta (n)
Cannot determine from info
Theta (log n)
Find the time complexity of the nested loop:
for (int i = 1; i <= n; i *= 2) { // outer loop
for (int j = 1; j <= i; j++) {// inner loop
// constant work
}
}
O(n)
O (log n)
O (n log n)
O (n^2)
Find the complexity of:
T(n)=T (n/2) +T (n/4) + n
O (n log n)
O(logn)
O(n)
O(n^2)
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i*i; j++) {
for (int k = 1; k <= j; k++) {
// constant work
}
}
}
O(n^5)
O(n^4)
O(n^3)
O(n^2)
