Algorithm Analysis and Complexity Questions and Answers

Answer: A

The worst-case time is both \(O(N)\) and \(\Omega(N)\), that is \(\Theta(N)\).

The algorithm makes a single pass, comparing each element with its neighbour, so it does at most N − 1 comparisons, which is O(N). In the worst case, a sorted array (or one whose first violation is at the very end), every adjacent pair must be checked before the algorithm can answer, so it needs N − 1 comparisons, which is \(\Omega(N)\).

Any correct algorithm must look at every element in the worst case, since an unread element could break the order. So the worst-case cost is linear from both sides, and the options denying either bound are wrong.

Answer: A

\(T(n) = \Theta(n \log \log n)\).

Divide the recurrence by n and set \(S(n) = T(n)/n\):

\[ \begin{aligned} \frac{T(n)}{n} &= \frac{T(\sqrt{n})}{\sqrt{n}} + 1 \\ S(n) &= S(\sqrt{n}) + 1 \end{aligned} \]

Each step takes a square root, and n reaches a constant after \(\log \log n\) square roots (write \(n = 2^{2^{k}}\); each step halves k). So \(S(n) = \Theta(\log \log n)\) and \(T(n) = \Theta(n \log \log n)\). \(n \log n\) would come from halving n at each level instead of square-rooting it, and the \(n^{2}\) options overcount the work per level, which is n at every level of the recursion.

Answer: A

The solution is \(T(n) = \Theta(n^{2}2^{n})\).

Divide both sides by \(2^{n}\) and set \(S(n) = T(n)/2^{n}\):

\[ \begin{aligned} \frac{T(n)}{2^{n}} &= \frac{T(n-1)}{2^{n-1}} + n \\ S(n) &= S(n-1) + n \\ S(n) &= 1 + \frac{n(n+1)}{2} \end{aligned} \]

using \(S(0) = T(0) = 1\). So \(T(n) = 2^{n}\left(1 + n(n+1)/2\right) = \Theta(n^{2}2^{n})\).

\(\Theta(n2^{n})\) treats the added term as if it did not accumulate over the n levels, \((\log n)^{2}2^{n}\) grows too slowly, and \(4^{n}\) is far too fast, since the recurrence only doubles at each step.

Answer: A

The answer is \(T_{1}(n) = \Theta(n^{2})\).

Solve the inner recurrence first with the master theorem. For \(T_{2}\), a = 5 and b = 4, so \(n^{\log_{4} 5} \approx n^{1.16}\), which grows faster than \(\log_{2} n\):

\[ T_{2}(n) = \Theta(n^{\log_{4} 5}) \]

For \(T_{1}\), a = 4 and b = 2, so the leaves contribute \(n^{\log_{2} 4} = n^{2}\). The added term \(T_{2}(n) = \Theta(n^{1.16})\) is polynomially smaller than \(n^{2}\), so the first case applies:

\[ T_{1}(n) = \Theta(n^{2}) \]

The extra \(\log_{2} n\) factor would appear only if the added term were \(\Theta(n^{2})\). The options with \(n^{\log_{4} 5}\) give the order of \(T_{2}\), not \(T_{1}\).

Answer: C

The loop invariant is \(X^{Y} = \mathrm{res} * a^{b}\).

Check that it holds at the start and is preserved by each branch:

• Initially \(\mathrm{res} = 1\), \(a = X\), \(b = Y\), so \(\mathrm{res} \cdot a^{b} = X^{Y}\).
• If \(b\) is even, \(a\) becomes \(a^{2}\) and \(b\) becomes \(b/2\): \((a^{2})^{b/2} = a^{b}\), unchanged.
• If \(b\) is odd, \(\mathrm{res}\) becomes \(\mathrm{res} \cdot a\) and \(b\) becomes \(b - 1\): \(\mathrm{res} \cdot a \cdot a^{b-1} = \mathrm{res} \cdot a^{b}\), unchanged.

When the loop ends, \(b = 0\), so \(X^{Y} = \mathrm{res}\), which is what the function returns.

\(X^{Y} = a^{b}\) fails after the first odd step, when part of the power has moved into \(\mathrm{res}\). \(X^{Y} = (\mathrm{res} * a)^{b}\) raises \(\mathrm{res}\) to the power \(b\) as well, and \((\mathrm{res} * a)^{Y} = (\mathrm{res} * X)^{b}\) holds at the start but fails after the first even step, when \(a\) becomes \(X^{2}\) while \(b\) halves.

Answer: B

The missing expressions are (P) 1 and (Q) len1+1.

At each step, first holds X[i-1] and second the other value in the current two-value window. If X[i] equals second, it differs from the previous element, so the run of equal values ending at X[i] is X[i] alone: len1 becomes 1, which is (P). The window still has only two values, so len2 grows by one.

If X[i] is a new third value, the longest two-value subarray ending at X[i] is the run of equal values ending at X[i-1] (length len1) followed by X[i], so len2 becomes len1+1, which is (Q). Then len1 resets to 1.

(P) len1+1 would extend a run across a change of value, and (Q) len2+1 would keep three distinct values in the window, so the other options fail.

Answer: A

One comparison is enough: 1.

Pick any two elements and compare them. Since all elements are distinct, one is strictly smaller than the other, and the smaller one cannot be the largest element of the list. So it is an answer, found with a single comparison. Zero comparisons cannot work, because without comparing anything no element is known not to be the maximum.

N - 1 is the number of comparisons needed to find the largest element itself, which the question does not ask for. N and 2N - 1 are more than even that.

Answer: A

The increasing order is \(\log(n)\), \(n^{1/3}\), \(2^{\log(n)}\), \(\log(n!)\).

Simplify each function first:

• log(n) grows more slowly than any positive power of n;
• n^1/3 is a polynomial of degree 1/3;
• 2^{log n} with base-2 logarithms is exactly n;
• log(n!) is Θ(n log n) by Stirling's approximation.

So the order is log n, n^1/3, n, n log n. An order that puts n^1/3 below log n reverses the rule that every power beats a logarithm. Putting 2^{log n} first misses that it equals n, and putting it last ranks n above n log n.

Answer: A

The fastest algorithm takes Θ(n) in the worst case.

Write d_i = A[i+1] - A[i] for i = 1, ..., n - 1. The condition says d_i > d_j whenever i > j: the sequence of differences is strictly increasing. Strict increase of a whole sequence is equivalent to strict increase between each pair of neighbours, d_i+1 > d_i, because the relation > is transitive. So one pass computing the n - 1 differences and comparing neighbours suffices: O(n).

No algorithm can do better, since changing any single element of A can break the condition, so every element must be read: Ω(n). Checking all pairs (i, j) would take Θ(n²), and Θ(log n) is impossible for the same reason.

Answer: B

The function returns 5.

The first loop halves i from \(2^{40}\) until it reaches 1, counting the halvings: j ends as 40, which is \(\log_{2} n\).

The second loop halves j while it is greater than 1, counting in sum: j goes 40, 20, 10, 5, 2, 1. The body runs for 40, 20, 10, 5 and 2, so sum is 5, which is \(\lfloor \log_{2} 40 \rfloor\).

40 is the value of j after the first loop, not the returned sum. 4 and 6 come from miscounting the halvings: integer division takes 5 to 2 and 2 to 1, so the body runs at 5 and at 2 but not at 1.