This question tests AP Computer Science A skills in informal run-time analysis, focusing on nested loops that examine pairs. Informal run-time analysis involves recognizing common algorithmic patterns and their associated complexities. The countDifferentPairs method uses nested loops where the outer loop runs n times and the inner loop runs approximately n/2 times on average, examining all unique pairs of elements. Choice B is correct because the total number of pairs examined is n(n-1)/2, which simplifies to O(n²) complexity. Choice A (O(n)) is incorrect because it fails to account for the nested structure - a single loop would only allow examining each element once, not all pairs. To help students: Draw diagrams showing which pairs are examined for small arrays. Explain that examining all pairs of n items inherently requires O(n²) operations.

This question tests AP Computer Science A skills in informal run-time analysis, focusing on recursive algorithms with logarithmic complexity. Informal run-time analysis of recursive methods requires examining how the problem size changes with each recursive call and counting the total number of calls. In the provided code, each recursive call divides n by 2, continuing until n reaches 1, which happens after approximately log₂(n) divisions. Choice C is correct because halving the input at each step creates a logarithmic relationship - doubling the input size adds only one more recursive call, characteristic of O(log n) complexity. Choice A (O(n)) is incorrect because it would require the recursion depth to be proportional to n, but here we're dividing by 2 each time, not subtracting 1. To help students: Trace through specific values like n=8 (3 calls) and n=16 (4 calls) to see the logarithmic pattern. Connect this to binary search and other divide-and-conquer algorithms that exhibit similar O(log n) behavior.

This question tests AP Computer Science A skills in informal run-time analysis, focusing on selection and iteration. Informal run-time analysis involves estimating an algorithm's efficiency by examining its structure, such as loops and conditionals, to determine its Big O complexity. This recursive Fibonacci implementation makes two recursive calls for each non-base case, creating a binary tree of calls where the number of nodes approximately doubles at each level, resulting in exponential growth. Choice C is correct because the recursion tree has approximately 2ⁿ nodes (more precisely, about 1.618ⁿ due to overlapping subproblems), making the time complexity O(2ⁿ). Choice A (O(n)) is incorrect because it would only apply to an iterative or memoized solution that computes each Fibonacci number once, not this naive recursive approach. To help students: Draw recursion trees for small values of n, highlight repeated calculations (like fib(2) being computed multiple times), and contrast with dynamic programming solutions to show how memoization reduces exponential to linear complexity.

This question tests AP Computer Science A skills in informal run-time analysis, focusing on selection sort's nested loop structure. Informal run-time analysis involves recognizing standard sorting algorithms and their characteristic complexity patterns based on their implementation structure. In the provided selection sort code, the outer loop runs n-1 times, and for each iteration i, the inner loop searches through the remaining n-i elements to find the minimum, resulting in approximately n²/2 comparisons total. Choice C is correct because despite the decreasing inner loop iterations, the nested structure still yields O(n²) complexity, as the sum 1+2+...+(n-1) equals n(n-1)/2, which is quadratic. Choice B (O(log n)) is incorrect because logarithmic complexity requires dividing the problem size repeatedly, but selection sort examines every remaining element in each pass. To help students: Trace through small arrays to see how selection sort always makes the same number of comparisons regardless of initial ordering. Emphasize that both selection sort and bubble sort have O(n²) complexity due to their nested loop structures.

This question tests AP Computer Science A skills in informal run-time analysis, focusing on recursive algorithms with exponential reduction. Informal run-time analysis of recursive methods requires understanding how the problem size changes with each recursive call. The countHalves method repeatedly divides n by 2 until reaching the base case, making approximately log₂(n) recursive calls. Choice C is correct because halving the input at each step is the hallmark of logarithmic complexity - doubling n only adds one more recursive call. Choice A (O(n)) is incorrect because it would require the recursion depth to be proportional to n, but here we're dividing by 2, not subtracting 1. To help students: Trace the execution for powers of 2 (n=8, 16, 32) to see the pattern. Connect this to binary search and other divide-and-conquer algorithms.

This question tests AP Computer Science A skills in informal run-time analysis, focusing on selection and iteration. Informal run-time analysis involves estimating an algorithm's efficiency by examining its structure, such as loops and conditionals, to determine its Big O complexity. The recursive method makes exactly n recursive calls (from n down to 0), with each call performing a constant amount of work (one addition and one recursive call). Choice A is correct because the recursion depth is n, and each level does O(1) work, resulting in O(n) total time complexity - essentially equivalent to a loop from 1 to n. Choice D (O(n²)) is incorrect because there's no nested iteration or multiple recursive calls per level that would create quadratic behavior. To help students: Draw recursion trees to visualize the call stack, relate recursive solutions to their iterative equivalents, and emphasize that single recursive calls typically maintain the same complexity as the recursion depth.

This question tests AP Computer Science A skills in informal run-time analysis, focusing on identifying dominant factors in algorithm complexity. Informal run-time analysis requires recognizing which structural elements most significantly impact performance. The sumGrid method contains nested loops that iterate through all n² elements of the matrix, with the if-statement inside being a constant-time operation. Choice A is correct because the two nested loops over n rows and n columns create O(n²) complexity - every element must be visited regardless of its value. Choice B is incorrect because the if-statement doesn't reduce the number of elements examined; it only determines whether to add each value. To help students: Emphasize that conditional statements inside loops don't change the loop's iteration count. Practice identifying the primary loop structure as the dominant factor in complexity analysis.

This question tests AP Computer Science A skills in informal run-time analysis, focusing on 2D array traversal with nested loops. Informal run-time analysis requires understanding how multiple dimensions affect complexity, particularly when processing grid-like data structures. In the provided code, the outer loop iterates through n rows, and the inner loop iterates through n columns (since rows=cols=n), resulting in n×n = n² total cell visits. Choice B is correct because visiting every cell in an n×n grid requires O(n²) operations, as each of the n² cells must be examined exactly once to compute the sum. Choice A (O(n)) is incorrect because it would only account for processing a single row or column, not the entire 2D grid, missing the multiplicative effect of the nested loops. To help students: Visualize small grids (like 3×3 or 4×4) and count the total cells to see the quadratic relationship. Explain that for square matrices, the complexity is based on the total number of elements, which is n².

This question tests AP Computer Science A skills in informal run-time analysis, focusing on selection sort implementation. Informal run-time analysis requires understanding how nested loops in sorting algorithms contribute to complexity. The selection sort uses two nested loops: the outer loop runs n-1 times to place each element, and the inner loop finds the minimum among remaining elements, performing approximately n²/2 comparisons total. Choice B is correct because the nested loop structure results in O(n²) complexity - for each position, we scan all remaining elements to find the minimum. Choice A (O(n)) is incorrect because finding the minimum of unsorted elements requires examining all of them, preventing linear complexity. To help students: Trace through the algorithm with a small array, counting comparisons. Compare selection sort with bubble sort to show both have O(n²) complexity despite different approaches.

This question tests AP Computer Science A skills in informal run-time analysis, focusing on algorithms that check all pairs. Informal run-time analysis requires recognizing that examining all pairs of elements has quadratic complexity. The hasPairSum method uses nested loops where each element is paired with every subsequent element, checking approximately n²/2 pairs in the worst case. Choice B is correct because despite the early return on success, the worst-case scenario (no valid pair) requires checking all possible pairs, resulting in O(n²) complexity. Choice A (O(n)) is incorrect because a single pass cannot check all possible pairs - you need nested iteration. To help students: Explain that early termination affects average case but not worst-case complexity. Use small examples to count the exact number of pairs checked.