Algorithm Analysis and Complexity Questions and Answers

Answer: C

The first function (n log n + n^2)(n^3 + 2) is dominated by n^2 x n^3 = n^5 since n log n is smaller than n^2 and 2 is smaller than n^3, so it is O(n^5). The second, (n! + 2^n)(n^3 + log(n^2 + 1)), has n! growing faster than 2^n and n^3 faster than the logarithm, so it is O(n^3 x n!). The pair is O(n^5) and O(n^3 x n!), option (C). Options (A) and (D) keep a lower order term, 2n^2, which a big-O estimate drops, and (B) and (D) give 2^n in place of n! in the second function, which understates its growth because n! is much larger than 2^n.

Answer: D

The solution is \(O(\log n \log \log n)\), which is option (D). Put \(m = \log n\); then \(T(2^{m}) = 2T(2^{m/2}) + m\). Writing \(S(m) = T(2^{m})\) gives

\[ S(m) = 2S(m/2) + m \]

which, by the master theorem, is \(\Theta(m \log m)\). Going back to \(n\):

\[ T(n) = \Theta(\log n \log \log n) \]

The bounds with a factor n in (A) and (B) are far too large, and \(O(\log \log n)\) in (C) is too small, since the term \(\log n\) is added at the top level.

Answer: C

The recurrence \(T(n) = T(n/3) + T(2n/3) + O(n)\) has the solution \(O(n \lg n)\). In the recursion tree each level does at most cn work in total, since the sizes n/3 and 2n/3 add up to n. The longest path shrinks by the factor 2/3 each step, so the depth is about \(\log_{3/2} n\).

\[ T(n) = O(cn \cdot \log_{3/2} n) = O(n \lg n) \]

The options \(O(\lg n)\) and \(O(n)\) ignore the work done at each of the levels, and \(O(n^{2})\) is an overestimate.

Answer: B

The estimates are \(O(n^{n})\) for \(n!\) and \(O(n \log n)\) for \(\log n!\). Since \(n! = 1 \cdot 2 \cdots n\) is at most \(n \cdot n \cdots n = n^{n}\), \(n!\) is \(O(n^{n})\), and taking logarithms gives \(\log n! \le n \log n\), so \(\log n!\) is \(O(n \log n)\). The options that give \(O(n!)\) for \(n!\) are trivially true but not the estimate of the key, and \(O(\log n!)\) merely repeats the function.

Answer: B

The time complexity is the maximum of h(n) and g(n). When an algorithm is made of two modules run one after the other, its running time is the sum h(n) + g(n), and for the order of growth the sum is dominated by the larger term, so it is of the order of max(h(n), g(n)). The minimum would ignore the slower module and the product would apply only if one module were run inside the other, so those are wrong.

Answer: B

\(E_{1}\) is correct and \(E_{2}\) is not correct.

For \(E_{1}\), \(n^{K} \lg n\) is of lower order than \(n^{K+\epsilon}\) for every \(\epsilon \gt 0\), so the sum is \(\Theta(n^{K+\epsilon})\). For \(E_{2}\), \(3^{n}\) grows faster than \(2^{n}\) by an exponential factor, so \(6n^{2}3^{n}\) is not \(O(n^{3}2^{n})\).

So options that call \(E_{1}\) false or \(E_{2}\) true are wrong.

Answer: C

The solution is \(O(n)\).

Here \(a = 3\), \(b = 4\), and \(n^{\log_4 3} \approx n^{0.79}\) is smaller than the added work \(f(n) = n\). By case 3 of the master theorem, with the regularity condition \(3(n/4) \le (3/4)n\) holding, \(T(n) = \Theta(n)\), hence \(O(n)\).

\(O(n^{2})\) and \(O(n \lg n)\) are not tight, and \(O(\lg n)\) is too small. Check the master theorem condition: \(f(n) = n = \Omega(n^{0.79 + \epsilon})\) for a small \(\epsilon \gt 0\), and \(3 f(n/4) = 3n/4 \le c f(n)\) with \(c = 3/4 \lt 1\), so case 3 applies and the solution is of the order of \(f(n)\), that is \(n\).