Algorithm Analysis and Complexity Questions and Answers

Q: The correct ordering of the growth rates \(3^{n}\), \(n^{3}\), \(3^{3}\), \(\log_{3} n\) is :

The correct order is \(3^{3},\ \log_{3} n,\ n^{3},\ 3^{n}\).\(3^{3} = 27\) is a constant, which does not grow at all. A logarithm grows, but more slowly than any power of n. A polynomial \(n^{3}\) grows more slowly than any exponential function, so \(3^{n}\) is the fastest:\[ O(1) \lt O(\log n) \lt O(n^{3}) \lt O(3^{n}) \]Options (A) and (B) put \(\log_{3} n\) below a constant, which is wrong for large n, and (A) also puts the constant after \(n^{3}\). Option (C) puts \(3^{n}\) before \(n^{3}\), but the exponential eventually outgrows any polynomial.

Q: If \(f(n) = 4n^{2}\) for all n and \(g(n) = n\) if \(n \gt 100\) and \(n^{3}\) if \(n \le 100\), then :

The answer is \(g(n)\) is of \(O(f(n))\).Big-O describes behaviour for large n. For \(n \gt 100\), \(g(n) = n\) while \(f(n) = 4n^{2}\), and \(n \le 4n^{2}\) for all such n, so \(g(n) = O(f(n))\). The definition of \(n^{3}\) for small n does not matter, because only values beyond some threshold count.For the same reason \(f(n) = 4n^{2}\) grows faster than \(g(n) = n\), so \(f(n)\) is not \(O(g(n))\), \(g(n)\) is not \(\Omega(f(n))\), and hence not \(\theta(f(n))\).

Q: Let S be a sorted array of n integers. Let T(n) denote the time taken by the most efficient algorithm to determine if there are two elements in S with sum greater than m, then :

T(n) is \(\theta(1)\).Because S is sorted, the largest possible sum of two elements is the sum of the two largest elements, S[n-1] + S[n-2]. If that sum is greater than m, the required pair exists; if it is not, no other pair can have a larger sum, so none exists.One addition and one comparison settle the question whatever n is, so the time is constant. A linear scan, \(\theta(n)\), or a binary search, \(\theta(\log n)\), does unnecessary work, and the time has nothing to do with the size of m.

Q: If(n) = 2 ×n2 + 5 × n + 3, then big Oh notation for the function f(n) is

The function is O(n2), which is not offered, so the answer is None of the above.Big O keeps the fastest-growing term and drops constants. For n ≥ 1:\[ \begin{aligned} f(n) &= 2n^{2} + 5n + 3 \\ &\le 2n^{2} + 5n^{2} + 3n^{2} = 10n^{2} \end{aligned} \]So f(n) = O(n2). O(n), O(log n) and O(1) all grow more slowly than n2, so none of them can bound f(n) for large n.

Q: Which of the following cannot be solved by recursion ?

The answer is All of the above can be solved by recursion.Each is defined in terms of a smaller case of itself:Fibonacci: F(n) = F(n-1) + F(n-2), with F(0) = 0 and F(1) = 1.Factorial: n! = n × (n-1)!, with 0! = 1.Power: xn = x × xn-1, with x0 = 1.Each has a base case that stops the recursion, so a recursive function solves all three, and none of the first three options is a problem recursion cannot handle.

Q: Which of the following can be used to solve the Tower of Hanoi Problem ?

The Tower of Hanoi is solved by Recursion.To move n discs from peg A to peg C: move the top n-1 discs to peg B, move the largest disc to C, then move the n-1 discs from B onto C. Each step uses the same procedure on one disc fewer, ending with a single disc, and it takes 2n - 1 moves.'Procedural' is a programming style, not a method of solution. The recursive solution does break the problem into smaller ones, but they are the same problem one disc smaller, done one after the other, which is why it is the standard example of recursion rather than of divide and conquer.

11.

Which one of the following statements is TRUE for all positive functions \(f(n)\)?

A.\(f(n^{2}) = \theta(f(n)^{2})\), when \(f(n)\) is a polynomial
B.\(f(n^{2}) = o(f(n)^{2})\)
C.\(f(n^{2}) = O(f(n)^{2})\), when \(f(n)\) is an exponential function
D.\(f(n^{2}) = \Omega(f(n)^{2})\)

Exam Year(s)

GATE CS - 2022,

Answer: A

The true statement is \(f(n^{2}) = \theta(f(n)^{2})\) when \(f(n)\) is a polynomial.

If \(f(n)\) is a polynomial of degree \(d\) with leading coefficient \(c \gt 0\), then \(f(n^{2})\) grows like \(c\,n^{2d}\) and \(f(n)^{2}\) grows like \(c^{2} n^{2d}\). They differ only by a constant factor, so each is \(\theta\) of the other.

The others fail for some positive function. For \(f(n) = n\), \(f(n^{2}) = n^{2} = f(n)^{2}\), which is not \(o(f(n)^{2})\). For \(f(n) = 2^{n}\), \(f(n^{2}) = 2^{n^{2}}\) outgrows \(f(n)^{2} = 2^{2n}\), so it is not \(O(f(n)^{2})\). For \(f(n) = \log n\), \(f(n^{2}) = 2\log n\) grows slower than \((\log n)^{2}\), so it is not \(\Omega(f(n)^{2})\).

Discuss in Forum

12.

The correct ordering of the growth rates \(3^{n}\), \(n^{3}\), \(3^{3}\), \(\log_{3} n\) is :

A.\(\log_{3} n,\ n^{3},\ 3^{3},\ 3^{n}\)
B.\(\log_{3} n,\ 3^{3},\ n^{3},\ 3^{n}\)
C.\(3^{3},\ \log_{3} n,\ 3^{n},\ n^{3}\)
D.\(3^{3},\ \log_{3} n,\ n^{3},\ 3^{n}\)

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

Answer: D

The correct order is \(3^{3},\ \log_{3} n,\ n^{3},\ 3^{n}\).

\(3^{3} = 27\) is a constant, which does not grow at all. A logarithm grows, but more slowly than any power of n. A polynomial \(n^{3}\) grows more slowly than any exponential function, so \(3^{n}\) is the fastest:

\[ O(1) \lt O(\log n) \lt O(n^{3}) \lt O(3^{n}) \]

Options (A) and (B) put \(\log_{3} n\) below a constant, which is wrong for large n, and (A) also puts the constant after \(n^{3}\). Option (C) puts \(3^{n}\) before \(n^{3}\), but the exponential eventually outgrows any polynomial.

Discuss in Forum

13.

If \(f(n) = 4n^{2}\) for all n and \(g(n) = n\) if \(n \gt 100\) and \(n^{3}\) if \(n \le 100\), then :

A.\(g(n)\) is of \(O(f(n))\)
B.\(g(n)\) is of \(\Omega(f(n))\)
C.\(f(n)\) is of \(O(g(n))\)
D.\(g(n)\) is of \(\theta(f(n))\)

Exam Year(s)

MH SET - 2020, SET Exam - 2020,

Answer: A

The answer is \(g(n)\) is of \(O(f(n))\).

Big-O describes behaviour for large n. For \(n \gt 100\), \(g(n) = n\) while \(f(n) = 4n^{2}\), and \(n \le 4n^{2}\) for all such n, so \(g(n) = O(f(n))\). The definition of \(n^{3}\) for small n does not matter, because only values beyond some threshold count.

For the same reason \(f(n) = 4n^{2}\) grows faster than \(g(n) = n\), so \(f(n)\) is not \(O(g(n))\), \(g(n)\) is not \(\Omega(f(n))\), and hence not \(\theta(f(n))\).

Discuss in Forum

14.

Let S be a sorted array of n integers. Let T(n) denote the time taken by the most efficient algorithm to determine if there are two elements in S with sum greater than m, then :

A.T(n) is of \(\theta(1)\)
B.T(n) is of \(\theta(m)\)
C.T(n) is of \(\theta(n)\)
D.T(n) is of \(\theta(\log n)\)

Exam Year(s)

MH SET - 2023, SET Exam - 2023,

Answer: A

T(n) is \(\theta(1)\).

Because S is sorted, the largest possible sum of two elements is the sum of the two largest elements, S[n-1] + S[n-2]. If that sum is greater than m, the required pair exists; if it is not, no other pair can have a larger sum, so none exists.

One addition and one comparison settle the question whatever n is, so the time is constant. A linear scan, \(\theta(n)\), or a binary search, \(\theta(\log n)\), does unnecessary work, and the time has nothing to do with the size of m.

Discuss in Forum

15.

If(n) = 2 ×n² + 5 × n + 3, then big Oh notation for the function f(n) is

A.O(n)
B.O(log n)
C.O(1)
D.None of the above

Exam Year(s)

Tripura Public Service Commission - 2019,

Answer: D

The function is O(n²), which is not offered, so the answer is None of the above.

Big O keeps the fastest-growing term and drops constants. For n ≥ 1:

\[ \begin{aligned} f(n) &= 2n^{2} + 5n + 3 \\ &\le 2n^{2} + 5n^{2} + 3n^{2} = 10n^{2} \end{aligned} \]

So f(n) = O(n²). O(n), O(log n) and O(1) all grow more slowly than n², so none of them can bound f(n) for large n.

Discuss in Forum

16.

Which of the following cannot be solved by recursion ?

A.Fibonacci series
B.Factorial of a number
C.Power function
D.All of the above can be solved by recursion

Exam Year(s)

Tripura Public Service Commission - 2019,

Answer: D

The answer is All of the above can be solved by recursion.

Each is defined in terms of a smaller case of itself:

Fibonacci: F(n) = F(n-1) + F(n-2), with F(0) = 0 and F(1) = 1.
Factorial: n! = n × (n-1)!, with 0! = 1.
Power: xⁿ = x × x^n-1, with x⁰ = 1.

Each has a base case that stops the recursion, so a recursive function solves all three, and none of the first three options is a problem recursion cannot handle.

Discuss in Forum

17.

Which of the following can be used to solve the Tower of Hanoi Problem ?

A.Recursion
B.Procedural
C.Divide and conquer
D.None of the above

Exam Year(s)

Tripura Public Service Commission - 2019,

Answer: A

The Tower of Hanoi is solved by Recursion.

To move n discs from peg A to peg C: move the top n-1 discs to peg B, move the largest disc to C, then move the n-1 discs from B onto C. Each step uses the same procedure on one disc fewer, ending with a single disc, and it takes 2ⁿ - 1 moves.

'Procedural' is a programming style, not a method of solution. The recursive solution does break the problem into smaller ones, but they are the same problem one disc smaller, done one after the other, which is why it is the standard example of recursion rather than of divide and conquer.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Algorithm Analysis and Complexity Questions and Answers || Algorithm Analysis and Complexity MCQ Questions and Answers || Algorithm Analysis and Complexity GK Questions and Answers || Algorithm Analysis and Complexity GK MCQ Questions || Algorithm Analysis and Complexity Multiple Choice Questions and Answers || Algorithm Analysis and Complexity GK || GK on Algorithm Analysis and Complexity || Data Structures and Algorithms Questions and Answers || Data Structures and Algorithms MCQ Questions and Answers || Data Structures and Algorithms GK Questions and Answers || GK on Data Structures and Algorithms

Algorithm Analysis and Complexity Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications