Consider the following functions from positive integers t real numbers:\(10,\sqrt n ,\;n,{\log _2}n,\frac{{100}}{n}\)The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:

\(10.\frac{{100}}{n},\;\sqrt {n,} {\log _2}n,\;n\)

\({\log _2}n,\frac{{100}}{n},\;10\;,\sqrt n ,\;n\)

\(\frac{{100}}{n},\;10\;,{\log _2}n,\;\sqrt n ,\;n\)

\(10.\frac{{100}}{n},\;\sqrt {n,} {\log _2}n,\;n\)

\(\frac{{100}}{n},{\log _2}n,\;10,\sqrt n ,\;n\)

If algorithm A and another algorithm B take log2(n) and √n microseconds, respectively, to solve a problem, then the largest size n of a problem these algorithms can solve. respectively. in one second are_____ and _____.

\({2^{{{10}^6}}}and\;{6.10^6}\)

\({2^{{{10}^6}}}and\;{10^{{12}}}\)

\({2^{{{10}^6}}}and\;{6.10^6}\)

\({2^{{{10}^6}}}and\;{6.10^{12}}\)

For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers:\(T\left( n \right) = a.T\left( {\frac{n}{b}} \right) + f\left( n \right)\)Which one of the following options is correct about the recurrence T(n)?

If f(n) is θ(nlogb(a)), then T(n) is θ(nlogb(a))

If f(n) is \(\frac{n}{{{{\log }_2}(n)}}\), then T(n) is θ(log2(n)).

If f(n) is n log2(n), then T(n) is θ(n log2(n)).

If f(n) is O(nlogb(a) - ϵ) for some ϵ > 0, then T(n) is θ(nlogb(a)).

If f(n) is θ(nlogb(a)), then T(n) is θ(nlogb(a))

Consider the following pseudo code. What is the total number of multiplications to be performed?D = 2for i = 1 to n dofor j = i to n dofor k = j + 1 to n doD = D * 3

Half of the product of the 3 consecutive integers.

One-third of the product of the 3 consecutive integers.

One-sixth of the product of the 3 consecutive integers.

Match the algorithms with their time complexities: Algorithm Time complexity(P)Towers of Hanoi with n disks(i)Θ (n2)(Q)Binary search given n sorted numbers(ii)Θ (n log n)(R)Heap sort given n numbers at the worst case(iii)Θ (2n)(S)Addition of two n × n matrices(iv)Θ (log n)

P – (iv), Q – (iii), R – (ii), S – (i)

P – (iii), Q – (iv), R – (i), S – (ii)

P – (iv), Q – (iii), R – (i), S – (ii)

P – (iii), Q – (iv), R – (ii), S – (i)

P – (iv), Q – (iii), R – (ii), S – (i)

22 + Mcqs in Asymptotic Worst Case Time And Time Complexity in Data Structures and Algorithms Page 1 McqOptions

1.	Consider the following segment of C codeint j, n;j = 1;while (j<=n) j = j*2;The number of comparisons made in the execution of the loop for any n > 0 is
A.	\(⌊log_2 n⌋^* n\)
B.	\(n\)
C.	\(⌊log_2 n⌋\)
D.	\(⌊log_2 n⌋+1\)
Answer» E.

Discussion

2.	Consider the following functions from positive integers t real numbers:\(10,\sqrt n ,\;n,{\log _2}n,\frac{{100}}{n}\)The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
A.	\({\log _2}n,\frac{{100}}{n},\;10\;,\sqrt n ,\;n\)
B.	\(\frac{{100}}{n},\;10\;,{\log _2}n,\;\sqrt n ,\;n\)
C.	\(10.\frac{{100}}{n},\;\sqrt {n,} {\log _2}n,\;n\)
D.	\(\frac{{100}}{n},{\log _2}n,\;10,\sqrt n ,\;n\)
Answer» C. \(10.\frac{{100}}{n},\;\sqrt {n,} {\log _2}n,\;n\)

Discussion

3.	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))
A.	Only I
B.	Only II
C.	Both I and II
D.	Neither I nor II
Answer» E.

Discussion

4.	Consider the algorithm that solves problems of size n by recursively solving two sub problems of size n - 1 and then combining the solutions in constant time. Then the running time of the algorithm would be:
A.	O(2n)
B.	O(logn)
C.	O(nlogn)
D.	O(n2)
Answer» B. O(logn)

Discussion

5.	Consider the following three functions.f1 = 10n f2 = nlogn f3 = n√nWhich one of the following options arranges the functions in the increasing order of asymptotic growth rate?
A.	f1 , f2, f3
B.	f2, f1, f3
C.	f3, f2, f1
D.	f2, f3, f1
Answer» E.

Discussion

6.	If algorithm A and another algorithm B take log2(n) and √n microseconds, respectively, to solve a problem, then the largest size n of a problem these algorithms can solve. respectively. in one second are_____ and _____.
A.	\({2^{{{10}^6}}}and\;{10^6}\)
B.	\({2^{{{10}^6}}}and\;{10^{{12}}}\)
C.	\({2^{{{10}^6}}}and\;{6.10^6}\)
D.	\({2^{{{10}^6}}}and\;{6.10^{12}}\)
Answer» C. \({2^{{{10}^6}}}and\;{6.10^6}\)

Discussion

7.	If positive function f(n) is given below as:f(n) = a0 + a1n + a2n2 + a3n3 + .......amnm then for positive n and am > 0, f(n) is:
A.	θ(na)
B.	θ(mn)
C.	θ(am)
D.	θ(nm)
Answer» E.

Discussion

8.	Consider the equality \(\mathop \sum \limits_{i = 0}^n {i^3} = X\) and the following choices for
A.	Only I
B.	Only II
C.	I or III or IV but not II
D.	II or III or IV but not I
Answer» D. II or III or IV but not I

Discussion

9.	Consider the following C function.int fun1(int n) {int i, j, k, p, q = 0;for (i = 1; i p = 0;for (j = n; j > 1; j = j/2) ++ p;for (k = 1; k ++ q;}return q;}Which one of the following most closely approximates the return value of the function fun1?
A.	n3
B.	n(log2)
C.	n log n
D.	n log (log n)
Answer» E.

Discussion

10.	Consider the following recurrenceT(n) = 2T(\(\sqrt n\)) + 1T(1) = 1Which of the following is true?
A.	T(n) = O(log log n)
B.	T(n) = O(log n)
C.	T(n) = O(\(\sqrt n\))
D.	T(n) = O(n)
Answer» C. T(n) = O(\(\sqrt n\))

Discussion

11.	In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a, b]? Assume that the number of reported elements is k.
A.	Θ(log n)
B.	Θ(log n + k)
C.	Θ(k log n)
D.	Θ(n log k)
Answer» C. Θ(k log n)

Discussion

12.	For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers:\(T\left( n \right) = a.T\left( {\frac{n}{b}} \right) + f\left( n \right)\)Which one of the following options is correct about the recurrence T(n)?
A.	If f(n) is \(\frac{n}{{{{\log }_2}(n)}}\), then T(n) is θ(log2(n)).
B.	If f(n) is n log2(n), then T(n) is θ(n log2(n)).
C.	If f(n) is O(nlogb(a) - ϵ) for some ϵ > 0, then T(n) is θ(nlogb(a)).
D.	If f(n) is θ(nlogb(a)), then T(n) is θ(nlogb(a))
Answer» D. If f(n) is θ(nlogb(a)), then T(n) is θ(nlogb(a))

Discussion

13.	An algorithm with three nested loops will have a Big-O efficiency of (a size on n).
A.	O(n3)
B.	O(3n)
C.	O(n4)
D.	O(n2)
Answer» B. O(3n)

Discussion

14.	Consider the following pseudo code. What is the total number of multiplications to be performed?D = 2for i = 1 to n dofor j = i to n dofor k = j + 1 to n doD = D * 3
A.	Half of the product of the 3 consecutive integers.
B.	One-third of the product of the 3 consecutive integers.
C.	One-sixth of the product of the 3 consecutive integers.
D.	None of the above
Answer» D. None of the above

Discussion

15.	An algorithm is made up of 2 modules M1 and M2.If order of M1 is f(n) and that of M2 is g (n), then the order of the algorithm is
A.	f(n) x g(n)
B.	f(n) + g (n)
C.	min (f(n), g(n))
D.	max (f(n), g (n))
Answer» E.

Discussion

16.	Consider the recurrence function \(T\left( n \right) = \left\{ {\begin{array}{*{20}{c}} {2T\left( {\sqrt n } \right) + 1,\;\;\;n > 2}\\ {2,\;\;\;0 < n \le 2} \end{array}} \right.\) Then T(n) in terms of Θ notation is
A.	Θ (log log n)
B.	Θ (log n)
C.	Θ (√n)
D.	Θ (n)
Answer» C. Θ (√n)

Discussion

17.	Consider the following C function.int fun(int n) { int i, j; for (i = 1; i < = n; i++) { for (j = 1; j < n; j + = i) { printf (‘’ %d %d’’, i, j); } }}Time complexity of fun in terms of Θ notation is
A.	Θ (n√n)
B.	Θ (n2)
C.	Θ (nlog n)
D.	Θ (n2log n)
Answer» D. Θ (n2log n)

Discussion

18.	For parameters a and b, both of which are ω(1), T(n) = T(n1/a) + 1, and T(b) = 1.Then T(n) is
A.	Θ(loga logb n)
B.	Θ(logab n)
C.	Θ(logb loga n)
D.	Θ(log2 log2 n)
Answer» B. Θ(logab n)

Discussion

19.	Consider the programvoid function(int n) {int i, j, count=0;for (i=n/2; i <= n; i++)for (j = 1; j <= n; j = j*2)count++;}The complexity of the program is
A.	O(log n)
B.	O(n2)
C.	O(n2logn)
D.	O(n log n)
Answer» E.

Discussion

20.	Consider the following recurrence relation.\(T(n) = \left\{ {\begin{array}{*{20}{c}} {T(n/2) + T(2n/5) + 7n \ \ \ if\ n > 0}\\ {1\ \ \ \ \ \ \ if\ n = 0} \end{array}} \right.\)Which one of the following option is correct?
A.	T(n) = Θ(n log n)
B.	T(n) = Θ(n5/2)
C.	T(n) = Θ((log n)5/2)
D.	T(n) = Θ(n)
Answer» E.

Discussion

21.	Match the algorithms with their time complexities: Algorithm Time complexity(P)Towers of Hanoi with n disks(i)Θ (n2)(Q)Binary search given n sorted numbers(ii)Θ (n log n)(R)Heap sort given n numbers at the worst case(iii)Θ (2n)(S)Addition of two n × n matrices(iv)Θ (log n)
A.	P – (iii), Q – (iv), R – (i), S – (ii)
B.	P – (iv), Q – (iii), R – (i), S – (ii)
C.	P – (iii), Q – (iv), R – (ii), S – (i)
D.	P – (iv), Q – (iii), R – (ii), S – (i)
Answer» D. P – (iv), Q – (iii), R – (ii), S – (i)

Discussion

22.	Consider the recurrence relation :\(T(n) = 8T \left(\frac{n}{2}\right)+Cn, if \;n > 1\)= b, if n = 1Where b and c are constants.The order of the algorithm corresponding to above recurrence relation is :
A.	n
B.	n2
C.	n lg n
D.	n3
Answer» E.

Discussion

Explore topic-wise MCQs in Data Structures and Algorithms.

Consider the following segment of C codeint j, n;j = 1;while (j<=n) j = j*2;The number of comparisons made in the execution of the loop for any n > 0 is

Consider the following functions from positive integers t real numbers:\(10,\sqrt n ,\;n,{\log _2}n,\frac{{100}}{n}\)The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:

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))

Consider the algorithm that solves problems of size n by recursively solving two sub problems of size n - 1 and then combining the solutions in constant time. Then the running time of the algorithm would be:

Consider the following three functions.f1 = 10n f2 = nlogn f3 = n√nWhich one of the following options arranges the functions in the increasing order of asymptotic growth rate?

If algorithm A and another algorithm B take log2(n) and √n microseconds, respectively, to solve a problem, then the largest size n of a problem these algorithms can solve. respectively. in one second are_ and _.

If positive function f(n) is given below as:f(n) = a0 + a1n + a2n2 + a3n3 + .......amnm then for positive n and am > 0, f(n) is:

Consider the equality \(\mathop \sum \limits_{i = 0}^n {i^3} = X\) and the following choices for

Consider the following C function.int fun1(int n) {int i, j, k, p, q = 0;for (i = 1; i p = 0;for (j = n; j > 1; j = j/2) ++ p;for (k = 1; k ++ q;}return q;}Which one of the following most closely approximates the return value of the function fun1?

Consider the following recurrenceT(n) = 2T(\(\sqrt n\)) + 1T(1) = 1Which of the following is true?

In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a, b]? Assume that the number of reported elements is k.

For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers:\(T\left( n \right) = a.T\left( {\frac{n}{b}} \right) + f\left( n \right)\)Which one of the following options is correct about the recurrence T(n)?

An algorithm with three nested loops will have a Big-O efficiency of (a size on n).

Consider the following pseudo code. What is the total number of multiplications to be performed?D = 2for i = 1 to n dofor j = i to n dofor k = j + 1 to n doD = D * 3

An algorithm is made up of 2 modules M1 and M2.If order of M1 is f(n) and that of M2 is g (n), then the order of the algorithm is

Consider the recurrence function \(T\left( n \right) = \left\{ {\begin{array}{*{20}{c}} {2T\left( {\sqrt n } \right) + 1,\;\;\;n > 2}\\ {2,\;\;\;0 < n \le 2} \end{array}} \right.\) Then T(n) in terms of Θ notation is

Consider the following C function.int fun(int n) { int i, j; for (i = 1; i < = n; i++) { for (j = 1; j < n; j + = i) { printf (‘’ %d %d’’, i, j); } }}Time complexity of fun in terms of Θ notation is

For parameters a and b, both of which are ω(1), T(n) = T(n1/a) + 1, and T(b) = 1.Then T(n) is

Consider the programvoid function(int n) {int i, j, count=0;for (i=n/2; i <= n; i++)for (j = 1; j <= n; j = j*2)count++;}The complexity of the program is

Consider the following recurrence relation.\(T(n) = \left\{ {\begin{array}{*{20}{c}} {T(n/2) + T(2n/5) + 7n \ \ \ if\ n > 0}\\ {1\ \ \ \ \ \ \ if\ n = 0} \end{array}} \right.\)Which one of the following option is correct?

Match the algorithms with their time complexities: Algorithm Time complexity(P)Towers of Hanoi with n disks(i)Θ (n2)(Q)Binary search given n sorted numbers(ii)Θ (n log n)(R)Heap sort given n numbers at the worst case(iii)Θ (2n)(S)Addition of two n × n matrices(iv)Θ (log n)

Consider the recurrence relation :\(T(n) = 8T \left(\frac{n}{2}\right)+Cn, if \;n > 1\)= b, if n = 1Where b and c are constants.The order of the algorithm corresponding to above recurrence relation is :