AP Computer Science a Quiz: Informal Run Time Analysis

What this quiz covers

This quiz focuses on Informal Run Time Analysis, giving you a quick way to practice the rules, question types, and explanations that matter most for AP Computer Science a.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

Question 1

public static int countDifferentPairs(int[] data) {
    int count = 0;
    for (int i = 0; i < data.length; i++) {
        for (int j = i + 1; j < data.length; j++) {
            if (data[i] != data[j]) {
                count++;
            }
        }
    }
    return count;
}

1. $O(n)$
2. $O(n^2)$ (correct answer)
3. $O(\log n)$
4. $O(1)$

Explanation: 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.

Question 2

public static int halveCount(int n) {
    if (n <= 1) {
        return 0;
    } else {
        return 1 + halveCount(n / 2);
    }
}

1. $O(n)$
2. $O(n^2)$
3. $O(\log n)$ (correct answer)
4. $O(1)$

Explanation: 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.

Question 3

public static int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

1. O(n)
2. O(log n)
3. O($2^n$) (correct answer)
4. O(1)

Explanation: 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.

Question 4

public static void selectionSort(int[] prices) {
    for (int i = 0; i < prices.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < prices.length; j++) {
            if (prices[j] < prices[minIndex]) {
                minIndex = j;
            }
        }
        int temp = prices[i];
        prices[i] = prices[minIndex];
        prices[minIndex] = temp;
    }
}

1. $O(n)$
2. $O(\log n)$
3. $O(n^2)$ (correct answer)
4. $O(1)$

Explanation: 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.

Question 5

public static int countHalves(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return 1 + countHalves(n / 2);
    }
}

1. $O(n)$
2. $O(1)$
3. $O(\log n)$ (correct answer)
4. $O(n^2)$

Explanation: 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.

Question 6

public static int sumToN(int n) {
    if (n <= 0) {
        return 0;
    }
    return n + sumToN(n - 1);
}
```​

1. O(n) (correct answer)
2. O(1)
3. O(log n)
4. O($n^2$)

Explanation: 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.

Question 7

public static int sumGrid(int[][] grid) {
    int sum = 0;
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[r].length; c++) {
            if (grid[r][c] > 0) {
                sum += grid[r][c];
            }
        }
    }
    return sum;
}

1. Two nested loops over $n$ rows and $n$ columns (correct answer)
2. The if-statement makes it constant time overall
3. Only the number of positive values matters, not $n$
4. Extra memory used by sum makes it $O(n)$ time

Explanation: 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.

Question 8

public static int totalPoints(int[][] board) {
    int sum = 0;
    for (int r = 0; r < board.length; r++) {
        for (int c = 0; c < board[0].length; c++) {
            if (board[r][c] > 0) {
                sum += board[r][c];
            }
        }
    }
    return sum;
}

1. $O(n)$
2. $O(n^2)$ (correct answer)
3. $O(1)$
4. $O(n \log n)$

Explanation: 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².

Question 9

public static void selectionSort(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] < nums[minIndex]) {
                minIndex = j;
            }
        }
        int temp = nums[i];
        nums[i] = nums[minIndex];
        nums[minIndex] = temp;
    }
}

1. $O(n)$
2. $O(n^2)$ (correct answer)
3. $O(\log n)$
4. $O(1)$

Explanation: 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.

Question 10

public static boolean hasPairSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return true;
            }
        }
    }
    return false;
}

1. $O(n)$
2. $O(n^2)$ (correct answer)
3. $O(1)$
4. $O(\log n)$

Explanation: 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.

Question 11

public static int findUser(String[] users, String target) {
    for (int i = 0; i < users.length; i++) {
        if (users[i].equals(target)) {
            return i;
        }
    }
    return -1;
}

1. It roughly doubles: $O(n)$ (correct answer)
2. It stays constant: $O(1)$
3. It roughly squares: $O(n^2)$
4. It roughly adds one step: $O(n-1)$

Explanation: 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.

Question 12

public static int fib(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

1. $O(n)$
2. $O(\log n)$
3. $O(2^n)$ (correct answer)
4. $O(n^2)$

Explanation: 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.

Question 13

public static int[][] multiply(int[][] a, int[][] b) {
    int n = a.length;
    int[][] c = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return c;
}

1. $O(n^2)$
2. $O(n^3)$ (correct answer)
3. $O(n)$
4. $O(1)$

Explanation: 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.

Question 14

public static int[][] multiply(int[][] a, int[][] b) {
    int n = a.length;
    int[][] c = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return c;
}
```​

1. O($n^2$)
2. O($n^3$) (correct answer)
3. O(n)
4. O(1)

Explanation: 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.

Question 15

public static int findId(int[] ids, int target) {
    for (int i = 0; i < ids.length; i++) {
        if (ids[i] == target) {
            return i;
        }
    }
    return -1;
}
```​

1. O(log n)
2. O(n) (correct answer)
3. O($n^2$)
4. O(1)

Explanation: 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.

Question 16

public static void bubbleSort(int[] scores) {
    for (int pass = 0; pass < scores.length - 1; pass++) {
        for (int i = 0; i < scores.length - 1 - pass; i++) {
            if (scores[i] > scores[i + 1]) {
                int temp = scores[i];
                scores[i] = scores[i + 1];
                scores[i + 1] = temp;
            }
        }
    }
}

1. $O(1)$
2. $O(n \log n)$
3. $O(n^2)$ (correct answer)
4. $O(n!)$

Explanation: This question tests AP Computer Science A skills in informal run-time analysis, focusing on nested loops in sorting algorithms. Informal run-time analysis involves examining the structure of an algorithm, particularly its loops and conditionals, to determine its Big O complexity. In the bubble sort implementation, there are two nested loops: the outer loop runs n-1 times, and the inner loop runs approximately n times on average, resulting in roughly n² comparisons. Choice C is correct because the nested loop structure means each element is compared with multiple other elements, leading to O(n²) complexity regardless of whether the array is already sorted. Choice B (O(n log n)) is incorrect because it represents the complexity of more efficient sorting algorithms like merge sort, not bubble sort's quadratic behavior. To help students: Practice tracing through algorithms with small inputs to count operations. Emphasize that nested loops often indicate polynomial complexity, with the degree equal to the nesting level.

Question 17

public static int minValue(int[] nums) {
    int min = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] < min) {
            min = nums[i];
        }
    }
    return min;
}

1. $O(\log n)$
2. $O(n)$ (correct answer)
3. $O(n^2)$
4. $O(1)$

Explanation: This question tests AP Computer Science A skills in informal run-time analysis, focusing on single-pass array algorithms. Informal run-time analysis involves counting the dominant operations relative to input size. The minValue method uses a single loop that examines each element exactly once, performing a constant-time comparison for each. Choice B is correct because the algorithm makes n-1 comparisons for an array of size n, resulting in O(n) linear complexity. Choice A (O(log n)) is incorrect because logarithmic complexity requires eliminating portions of the search space, which doesn't happen when we must examine every element. To help students: Emphasize that finding a minimum requires examining every element at least once. Compare with binary search to highlight why examining all elements prevents logarithmic complexity.

Question 18

public static void doublePrint(int n) {
    if (n == 0) {
        return;
    }
    System.out.println(n);
    doublePrint(n - 1);
    doublePrint(n - 1);
}

1. $O(n)$
2. $O(n^2)$
3. $O(2^n)$ (correct answer)
4. $O(\log n)$

Explanation: This question tests AP Computer Science A skills in informal run-time analysis, focusing on recursive algorithms with multiple recursive calls. Informal run-time analysis of recursive methods requires understanding how multiple recursive calls create exponential growth. The doublePrint method makes two recursive calls for each value from n down to 1, creating a binary tree of calls with depth n. Choice C is correct because each level doubles the number of calls, resulting in 2ⁿ total calls and O(2ⁿ) exponential complexity. Choice A (O(n)) is incorrect because it assumes linear growth, missing that each call spawns two more calls, not one. To help students: Draw the recursion tree for small values of n. Compare with fibonacci recursion to reinforce the pattern of exponential growth from multiple recursive calls.

Question 19

public static int[][] multiply(int[][] a, int[][] b) {
    int n = a.length;
    int[][] result = new int[n][n];
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            for (int k = 0; k < n; k++) {
                result[r][c] += a[r][k] * b[k][c];
            }
        }
    }
    return result;
}

1. $O(n^2)$
2. $O(n^3)$ (correct answer)
3. $O(n)$
4. $O(1)$

Explanation: This question tests AP Computer Science A skills in informal run-time analysis, focusing on matrix multiplication algorithms. Informal run-time analysis involves counting nested loops and understanding their iteration bounds. The matrix multiplication algorithm uses three nested loops, each iterating n times: one for result rows, one for result columns, and one for the dot product calculation. Choice B is correct because three nested loops, each running n times, results in n³ total operations and O(n³) complexity. Choice A (O(n²)) is incorrect because it accounts for only two dimensions, missing that each element of the result requires n multiplications. To help students: Walk through calculating a single element to see why it needs n operations. Emphasize that matrix multiplication inherently requires more work than element-wise operations.