Algorithm Time Complexity Analysis

Using Master Theorem: a=3, b=4, f(n)=n^2. Since n^(log_4(3)) ≈ n^0.79 < n^2, we're in Case 3 where f(n) dominates. Therefore T(n) = O(n^2). The recursive calls at each level contribute polynomial work, but the n^2 term at the root determines overall complexity.

The recurrence T(n) = T(n/3) + T(2n/3) + O(n) creates a highly unbalanced recursion tree where each level's work sums to O(n). The height is approximately log_(3/2)(n) because the larger branch shrinks by factor 2/3. Total work: O(n log n). This is correct.

Using Master Theorem: a=3, b=4, f(n)=n log n. Since n^(log_4(3)) ≈ n^0.79 < n log n, we're in Case 3 where f(n) dominates by a polynomial factor. Therefore T(n) = O(n log n), which matches the claimed answer B.

Using Master Theorem: a=9, b=3, f(n)=n. Critical exponent: log_3(9)=2, so n^(log_b(a))=n^2. Since f(n)=n < n^2, we're in Case 1 where the recursive part dominates. Therefore T(n) = O(n^2). This matches the claimed answer A - this recurrence represents 9 recursive calls each on 1/3 of the input.

The recurrence T(n) = T(2n/3) + 1 has one recursive call that reduces the problem size by factor 2/3, with constant work at each level. The height of the recursion tree is log_(3/2)(n) since we repeatedly multiply by 2/3. With constant work per level, total is O(log n). This matches the claimed answer D.

This recurrence decreases the problem size by 1 each step while adding 1/n. Expanding gives T(n) = T(0) + 1/1 + 1/2 + 1/3 + ... + 1/n. This sum is the harmonic series H_n, which grows logarithmically. The n² and n options are incorrect because the terms 1/n get progressively smaller, and n log n would require linearly growing terms.

Using the Master Theorem: a=4, b=2, so n^(log_b a) = n^2. The function f(n) = n²√n = n^2.5 is polynomially larger than n^2 (by factor n^0.5). Since the regularity condition a·f(n/b) ≤ c·f(n) holds, case 3 applies: T(n) = Θ(f(n)) = Θ(n²√n). The n log n option would only apply if f(n) = O(n^2), which is false here.

The recursion tree has log n levels, each contributing n/log(n/2^i). Level 0: n/log n, Level 1: n/log(n/2), ..., Level log n: O(log n). Using the integral approximation, the sum of n/log(n/2^i) for i=0 to log n is O(n log log n). This is because we're essentially summing 1/log(x) which gives the log log factor.

At each level, the total work is n + n/2 + n/4 + n/8 + ... (sum of T(n/2), T(n/4), T(n/8) contributions) plus the constant n at the root. The sum n(1 + 1/2 + 1/4 + 1/8 + ...) converges to 2n = O(n). The O(n²) option would require quadratic growth at each level, and O(log n) ignores the linear work at each node.

Using the Master Theorem for recurrence relations of the form T(n) = aT(n/b) + f(n), here a = 3, b = 2, and f(n) = n log n. Comparing f(n) = n log n with n^(log_b a) = n^(log_2 3), since log_2 3 is approximately 1.585, n^1.585 grows faster than n log n. Thus, Case 1 applies, yielding O(n^(log 3)).

This recurrence adds log n at each of n steps. Summing log 1 + log 2 + ... + log n = log(n!) ≈ n log n - n + O(log n) by Stirling's approximation. Therefore T(n) = O(n log n). The O(n) option would require constant work per step, and O(n²) would require linearly growing work.

This is the classic exponential recurrence. Expanding: T(n) = 2T(n-1) + 1 = 2(2T(n-2) + 1) + 1 = 4T(n-2) + 3 = 8T(n-3) + 7 = ... = 2^n T(0) + (2^n - 1). The dominant term is 2^n, so T(n) = O(2^n). The n² option would apply to T(n)=T(n-1)+n, and n^log 3 is for divide-and-conquer recurrences.

Kruskal's algorithm uses edge sorting and union-find. Sorting |E| edges takes O(|E| log |E|) ≈ O(|E| log |V|) since |E| ≤ |V|². Union-find operations are nearly O(1) with path compression and union by rank. The dominant cost is sorting, giving O(|E| log |V|). Adjacency list representation is standard.

Prim's algorithm on an adjacency matrix requires scanning all vertices to find the minimum weight edge, taking O(|V|) per vertex. With |V| iterations, total is O(|V|²). With Fibonacci heap + adjacency list, it becomes O(|E| + |V| log |V|), but O(|V|²) is the standard answer for basic implementation.

This recurrence adds approximately n at each of n steps (the constant c is negligible). Summing 1 + 2 + 3 + ... + n = n(n+1)/2 = O(n²). This is the formula for the sum of the first n integers. The O(n) option would require constant work per step like T(n)=T(n-1)+1, and O(2^n) would be for T(n)=2T(n-1)+c.

Prim's algorithm using a binary heap performs O(|E|) extract-min and O(|V|) decrease-key operations, each costing O(log|V|). The dominant term is |E|log|V| because the number of edges is typically greater than vertices. Option B incorrectly writes V as base and E as exponent, while C and D are not the correct complexity for heap-based Prim's.

Using the Master Theorem: T(n) = 2T(n/2) + n^2, we have a=2, b=2, f(n)=n^2. Since n^log_b(a) = n^1 and f(n) = n^2 = Ω(n^(1+ε)) for ε<1, this is Case 3. The regularity condition 2f(n/2) = n^2/2 ≤ cn^2 holds, so T(n) = Θ(n^2). Options B, C, and D do not match this result.

The recurrence T(n) = 2T(√n) + n log n + n requires a different technique. Let m = log n, then T(2^m) = 2T(2^(m/2)) + 2^m * m + 2^m. This recurrence doesn't yield any of the simple forms in options A, B, or C. The complexity involves polynomial-logarithmic terms that don't match the given options, making 'None of these' the correct choice.