This question tests AP Computer Science A skills in informal run-time analysis, focusing on linear search through iteration. Informal run-time analysis requires understanding how an algorithm's execution time scales with input size, particularly examining loop structures and their relationship to n. In the provided linear search code, a single loop iterates through the array once, checking each element until finding the target or reaching the end. Choice A is correct because when the input size doubles from n to 2n, the worst-case number of comparisons also doubles from n to 2n, maintaining a linear O(n) relationship. Choice C (O(n²)) is incorrect because it suggests quadratic growth, which would mean doubling the input would quadruple the time, but this algorithm has only one loop dependent on n. To help students: Use concrete examples like searching through 10 vs 20 items to visualize linear growth. Reinforce that "roughly doubles" describes linear complexity, while "roughly quadruples" would indicate quadratic complexity.

This question tests AP Computer Science A skills in informal run-time analysis, focusing on recursive algorithms with exponential complexity. Informal run-time analysis of recursive methods requires understanding the branching factor and depth of the recursion tree. In the provided Fibonacci code, each call (except base cases) makes two recursive calls, creating a binary tree of calls with depth approximately n, resulting in roughly 2ⁿ total function calls. Choice C is correct because the recursive structure creates an exponential growth pattern - each increase in n roughly doubles the number of function calls, characteristic of O(2ⁿ) complexity. Choice A (O(n)) is incorrect because it would require only n function calls total, but this naive recursive approach recalculates the same Fibonacci values many times. To help students: Draw the recursion tree for small values like fib(5) to visualize the exponential growth. Contrast this with dynamic programming solutions that achieve O(n) by avoiding redundant calculations.

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 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 matrix multiplication with triple nested loops. Informal run-time analysis of matrix operations requires understanding how each dimension contributes to the overall complexity. In the provided code, there are three nested loops, each running n times: i iterates through rows, j through columns, and k performs the dot product calculation, resulting in n³ total multiplication operations. Choice B is correct because the triple nested loop structure, where each loop depends on n, creates O(n³) complexity - for each of the n² elements in the result matrix, we perform n multiplications. Choice A (O(n²)) is incorrect because it would only account for visiting each cell in the result matrix once, but computing each cell requires n operations for the dot product. To help students: Visualize matrix multiplication for small matrices (like 2×2) to count operations. Explain that the number of loops often indicates the power of n in the complexity.

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. The matrix multiplication code contains three nested loops, each iterating n times, where n is the dimension of the square matrices being multiplied. Choice B is correct because the triple-nested structure results in n×n×n = n³ total operations, as each element of the result matrix requires n multiplications and additions. Choice A (O(n²)) is incorrect because it only accounts for the number of elements in the result matrix, not the n operations required to compute each element. To help students: Use small matrices (2×2 or 3×3) to count operations manually, emphasize that matrix multiplication inherently requires three indices (row, column, and summation), and discuss how the standard algorithm's O(n³) complexity has motivated research into faster methods.

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 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 provided code shows a linear search through an unsorted array, with a single for loop that iterates through each element once until finding the target or reaching the end. Choice B is correct because in the worst case (target not found or at the end), the algorithm must check all n elements, resulting in O(n) linear time complexity. Choice A (O(log n)) is incorrect because logarithmic complexity requires dividing the problem space (like binary search on sorted data), which isn't possible with unsorted data. To help students: Emphasize that single loops through data typically indicate O(n) complexity, discuss how early returns don't change worst-case analysis, and contrast linear search with binary search to reinforce the importance of data organization.

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.