AP Computer Science Principles Quiz: Algorithmic Efficiency

What this quiz covers

This quiz focuses on Algorithmic Efficiency, giving you a quick way to practice the rules, question types, and explanations that matter most for AP Computer Science Principles.

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

FIB_RECURSIVE(n)
  IF n <= 1
    RETURN n
  RETURN FIB_RECURSIVE(n-1) + FIB_RECURSIVE(n-2)

FIB_DP(n)
  IF n <= 1
    RETURN n
  prev <- 0
  curr <- 1
  FOR i <- 2 TO n
    next <- prev + curr
    prev <- curr
    curr <- next
  RETURN curr

1. Naive recursion, because it uses fewer variables and therefore runs in $O(n)$.
2. Dynamic programming, because $O(n)$ grows far slower than $O(2^n)$ as $n$ increases. (correct answer)
3. Naive recursion, because $O(2^n)$ is smaller than $O(n)$ for large $n$.
4. They are equivalent, because both compute the same Fibonacci values in the same steps.

Explanation: This question tests AP Computer Science Principles on algorithmic efficiency, specifically understanding exponential versus linear time complexity in recursive algorithms. Algorithmic efficiency refers to how effectively an algorithm performs in terms of time and space, often expressed using Big O notation to represent time complexity. In this passage, the comparison between naive recursive Fibonacci and dynamic programming highlights how memoization dramatically improves efficiency, with naive recursion having exponential O(2ⁿ) complexity while dynamic programming achieves linear O(n) complexity. Choice B is correct because it accurately identifies dynamic programming as more efficient, recognizing that O(n) grows far slower than O(2ⁿ) - for n=45, this is the difference between 45 operations versus over 35 trillion operations. This demonstrates understanding of exponential growth's severity. Choice C is incorrect because it claims O(2ⁿ) is smaller than O(n) for large n, which is backwards - exponential functions grow explosively compared to linear functions. This error often occurs when students misread the notation or don't understand exponential growth. To help students: Calculate actual values for small n to show exponential explosion (e.g., 2¹⁰=1024 vs 10). Trace through recursive calls to visualize repeated subproblems. Watch for: confusion about exponential notation or underestimating how quickly exponential functions grow.

Question 2

procedure linearSearch(sortedList, targetID)
  for index <- 1 to length(sortedList)
    if sortedList[index] = targetID
      return index
  return -1

procedure binarySearch(sortedList, targetID)
  low <- 1
  high <- length(sortedList)
  while low <= high
    mid <- (low + high) / 2
    if sortedList[mid] = targetID
      return mid
    else if sortedList[mid] < targetID
      low <- mid + 1
    else
      high <- mid - 1
  return -1

1. Linear search, because it checks items in order and avoids dividing the range.
2. Binary search, because $O(\log n)$ grows slower than $O(n)$ as $n$ increases. (correct answer)
3. Linear search, because $O(n)$ is the same as $O(\log n)$ for large lists.
4. Binary search, because it works best even when the list is not sorted.

Explanation: This question tests AP Computer Science Principles on algorithmic efficiency, specifically comparing search algorithm time complexities on sorted data. Algorithmic efficiency refers to how effectively an algorithm performs in terms of time and space, often expressed using Big O notation to represent time complexity. In this passage, the comparison between linear search and binary search on a sorted list highlights how binary search's O(log n) time complexity provides a massive advantage over linear search's O(n) when searching through up to 10,000,000 IDs. Choice B is correct because it accurately identifies binary search as more efficient for large inputs, due to its O(log n) time complexity growing much slower than O(n) as n increases. This demonstrates understanding that logarithmic growth is dramatically better than linear growth for large datasets. Choice D is incorrect because it claims binary search works on unsorted lists, which is false - binary search requires a sorted list to function correctly. This error often occurs when students memorize algorithm names without understanding their prerequisites. To help students: Calculate actual comparisons needed for both algorithms with n=10,000,000 (linear: up to 10 million, binary: about 23). Emphasize that binary search only works on sorted data. Watch for: students who forget the sorted list requirement or who don't grasp the dramatic difference between O(n) and O(log n) for large n.

Question 3

procedure DFS(graph, startVertex)
  stack <- [startVertex]
  visited <- emptySet
  while stack is not empty
    current <- pop(stack)
    if current not in visited
      add current to visited
      for each neighbor in graph[current]
        push(neighbor, stack)

procedure BFS(graph, startVertex)
  queue <- [startVertex]
  visited <- emptySet
  while queue is not empty
    current <- dequeue(queue)
    if current not in visited
      add current to visited
      for each neighbor in graph[current]
        enqueue(neighbor, queue)

1. DFS, because a stack makes it $O(V)$ while BFS remains $O(V+E)$.
2. BFS, because a queue guarantees $O(E)$ while DFS can be $O(V^2)$.
3. Neither, because both run in $O(V+E)$ on the same graph input. (correct answer)
4. DFS, because it always avoids processing edges once the first path is found.

Explanation: This question tests AP Computer Science Principles on algorithmic efficiency, specifically recognizing when two algorithms have identical time complexity. Algorithmic efficiency refers to how effectively an algorithm performs in terms of time and space, often expressed using Big O notation to represent time complexity. In this passage, both DFS and BFS algorithms are presented with the same O(V+E) time complexity for graph traversal, where they must visit all vertices and edges in the worst case. Choice C is correct because it accurately identifies that neither algorithm has lower time complexity - both run in O(V+E) on the same graph input, visiting each vertex and edge exactly once. This demonstrates understanding that different implementations can have the same asymptotic complexity. Choice A is incorrect because it claims DFS has O(V) complexity by using a stack, ignoring that edges must still be processed, maintaining the O(V+E) complexity. This error often occurs when students focus on data structure differences without analyzing the actual operations performed. To help students: Trace through both algorithms to show they perform the same fundamental operations - visiting vertices and examining edges. Explain that using a stack versus queue changes traversal order, not the total work done. Watch for: students who think different data structures automatically mean different time complexities or who ignore edge processing in their analysis.

Question 4

procedure bubbleSort(nameList)
  n <- length(nameList)
  for i <- 1 to n - 1
    for j <- 1 to n - i
      if nameList[j] > nameList[j + 1]
        swap(nameList[j], nameList[j + 1])

procedure mergeSort(nameList)
  if length(nameList) <= 1
    return nameList
  mid <- length(nameList) / 2
  left <- mergeSort(nameList[1..mid])
  right <- mergeSort(nameList[mid+1..end])
  return merge(left, right)

1. When nameList is large, because $O(n \log n)$ scales better than $O(n^2)$. (correct answer)
2. When nameList is tiny, because $O(n^2)$ grows slower than $O(n \log n)$.
3. When input size is irrelevant, because Big O ignores $n$ and focuses only on swaps.
4. When the list is unsorted, because merge sort becomes $O(n^2)$ in the worst case.

Explanation: This question tests AP Computer Science Principles on algorithmic efficiency, specifically understanding when different time complexities matter in practice. Algorithmic efficiency refers to how effectively an algorithm performs in terms of time and space, often expressed using Big O notation to represent time complexity. In this passage, the comparison between bubble sort (O(n²)) and merge sort (O(n log n)) highlights how the advantage of better time complexity becomes significant as input size grows, particularly when the list can reach 5,000 names. Choice A is correct because it accurately identifies that merge sort outperforms bubble sort when nameList is large, due to O(n log n) scaling better than O(n²) as n increases. This demonstrates understanding of how algorithmic efficiency impacts real-world performance. Choice B is incorrect because it reverses the relationship, claiming O(n²) grows slower than O(n log n), which is mathematically false. This error often occurs when students don't understand how to compare growth rates of different functions. To help students: Create tables showing actual values of n² vs n log n for various n values. Discuss that for small inputs (like 20 names), the difference may be negligible, but for larger inputs (like 5,000), it becomes significant. Watch for: students who think 'smaller' Big O always means faster regardless of input size, or who don't understand that both algorithms work correctly but differ in speed.

Question 5

procedure DFS(graph, startVertex)
  stack <- [startVertex]
  visited <- emptySet
  while stack is not empty
    current <- pop(stack)
    if current not in visited
      add current to visited
      for each neighbor in graph[current]
        push(neighbor, stack)

procedure BFS(graph, startVertex)
  queue <- [startVertex]
  visited <- emptySet
  while queue is not empty
    current <- dequeue(queue)
    if current not in visited
      add current to visited
      for each neighbor in graph[current]
        enqueue(neighbor, queue)

1. When the graph is large, because BFS is $O(\log V)$ while DFS is $O(V+E)$.
2. When exploring the same graph representation, because both are $O(V+E)$ in time complexity. (correct answer)
3. When the graph has many edges, because DFS becomes $O(V^2)$ but BFS stays $O(V+E)$.
4. When the start vertex is fixed, because DFS always revisits vertices more than BFS.

Explanation: This question tests AP Computer Science Principles on algorithmic efficiency, specifically understanding that different algorithms can have the same time complexity. Algorithmic efficiency refers to how effectively an algorithm performs in terms of time and space, often expressed using Big O notation to represent time complexity. In this passage, both DFS (Depth-First Search) and BFS (Breadth-First Search) are shown to have O(V+E) time complexity, where V is vertices and E is edges, demonstrating that they visit each vertex and edge once. Choice B is correct because it accurately identifies that when exploring the same graph representation, both algorithms have the same O(V+E) time complexity, meaning neither outperforms the other in terms of Big O analysis. This demonstrates understanding that different algorithms can have identical time complexities. Choice A is incorrect because it falsely claims BFS has O(log V) complexity, which would only be true for specific tree structures, not general graphs. This error often occurs when students confuse graph traversal with tree-specific operations. To help students: Emphasize that both DFS and BFS visit every reachable vertex exactly once and examine each edge. Explain that the choice between them depends on other factors like space complexity or specific problem requirements, not time complexity. Watch for: students who assume different algorithms must have different complexities or who confuse graph traversal with binary search trees.

Question 6

FIB_RECURSIVE(n)
  IF n <= 1
    RETURN n
  RETURN FIB_RECURSIVE(n-1) + FIB_RECURSIVE(n-2)

FIB_DP(n)
  IF n <= 1
    RETURN n
  prev <- 0
  curr <- 1
  FOR i <- 2 TO n
    next <- prev + curr
    prev <- curr
    curr <- next
  RETURN curr

1. When n is large, because it avoids repeated subproblems and runs in $O(n)$. (correct answer)
2. When n is small, because $O(2^n)$ decreases as n increases.
3. Only when n is even, because odd values force extra recursive calls.
4. Never, because loops are slower than recursion and make the runtime $O(n^2)$.

Explanation: This question tests AP Computer Science Principles on algorithmic efficiency, specifically understanding when dynamic programming outperforms naive recursion. Algorithmic efficiency refers to how effectively an algorithm performs in terms of time and space, often expressed using Big O notation to represent time complexity. In this passage, the comparison between naive recursive Fibonacci and dynamic programming shows how avoiding repeated calculations transforms exponential O(2ⁿ) complexity into linear O(n) complexity. Choice A is correct because it accurately identifies that dynamic programming outperforms naive recursion when n is large, specifically because it avoids recalculating the same Fibonacci values repeatedly and achieves O(n) time - for n=50, this means 50 operations versus approximately 1.1 quadrillion operations. This demonstrates understanding of memoization benefits. Choice B is incorrect because it claims O(2ⁿ) decreases as n increases, which is backwards - exponential functions increase extremely rapidly with n. This error often occurs when students misread exponential notation or don't understand that larger exponents mean faster growth, not slower. To help students: Draw the recursion tree for small n values to visualize repeated calculations. Show how dynamic programming stores and reuses results. Watch for: confusion about exponential growth direction or underestimating the impact of avoiding repeated work.

Question 7

procedure linearSearch(sortedList, targetTitle)
  for index <- 1 to length(sortedList)
    if sortedList[index] = targetTitle
      return index
  return -1

procedure binarySearch(sortedList, targetTitle)
  low <- 1
  high <- length(sortedList)
  while low <= high
    mid <- (low + high) / 2
    if sortedList[mid] = targetTitle
      return mid
    else if sortedList[mid] < targetTitle
      low <- mid + 1
    else
      high <- mid - 1
  return -1

1. Binary search, because $O(\log n)$ is always smaller than $O(n)$ for any $n$.
2. Linear search, because small $n$ can make the difference between $O(n)$ and $O(\log n)$ minor. (correct answer)
3. Binary search, because it runs in $O(n)$ time when the list is already sorted.
4. Linear search, because $O(n)$ becomes $O(1)$ whenever the target is near the end.

Explanation: This question tests AP Computer Science Principles on algorithmic efficiency, specifically understanding when simpler algorithms might be preferable despite worse Big O complexity. Algorithmic efficiency refers to how effectively an algorithm performs in terms of time and space, often expressed using Big O notation to represent time complexity. In this passage, the comparison between linear search (O(n)) and binary search (O(log n)) on small datasets (as small as 30 titles) highlights that Big O notation describes growth rates, not absolute performance for all input sizes. Choice B is correct because it accurately identifies that for small datasets, the difference between O(n) and O(log n) can be minor, and linear search's simpler implementation might even perform better due to lower overhead. This demonstrates understanding that Big O analysis is most relevant for large inputs. Choice A is incorrect because it claims O(log n) is always smaller than O(n) for any n, ignoring that for small values, implementation overhead and constant factors matter. This error often occurs when students treat Big O as an absolute measure rather than an asymptotic one. To help students: Show actual runtime comparisons for n=30 where linear search might complete in microseconds. Discuss how binary search's overhead (calculating midpoints, maintaining bounds) can outweigh benefits for small n. Watch for: students who think better Big O always means faster execution regardless of input size or implementation details.

Question 8

procedure bubbleSort(scoreList)
  n <- length(scoreList)
  for i <- 1 to n - 1
    for j <- 1 to n - i
      if scoreList[j] > scoreList[j + 1]
        swap(scoreList[j], scoreList[j + 1])

procedure mergeSort(scoreList)
  if length(scoreList) <= 1
    return scoreList
  mid <- length(scoreList) / 2
  left <- mergeSort(scoreList[1..mid])
  right <- mergeSort(scoreList[mid+1..end])
  return merge(left, right)

1. Bubble sort, because nested loops reduce comparisons as the list grows.
2. Merge sort, because $O(n \log n)$ grows slower than $O(n^2)$ for large $n$. (correct answer)
3. Bubble sort, because $O(n^2)$ is smaller than $O(n \log n)$ for large $n$.
4. Merge sort, because it is always faster regardless of input size or constraints.

Explanation: This question tests AP Computer Science Principles on algorithmic efficiency, specifically understanding and comparing algorithm time complexities. Algorithmic efficiency refers to how effectively an algorithm performs in terms of time and space, often expressed using Big O notation to represent time complexity. In this passage, the comparison between bubble sort and merge sort highlights how input size affects their time complexities, with bubble sort having a time complexity of O(n²) while merge sort has a time complexity of O(n log n). Choice B is correct because it accurately identifies merge sort as more efficient for large inputs, due to its lower time complexity of O(n log n), which grows much slower than O(n²) as n increases to 200,000. This demonstrates understanding of efficiency analysis. Choice C is incorrect because it misunderstands the relationship between O(n²) and O(n log n), incorrectly claiming that O(n²) is smaller for large n. This error often occurs when students misinterpret Big O notation or fail to understand how different functions grow. To help students: Use graphs to visualize how n², n log n, and other functions grow as n increases. Emphasize that for large values like 200,000, the difference between O(n²) and O(n log n) becomes dramatic. Watch for: students who memorize algorithm names without understanding their complexities or who confuse the meaning of 'smaller' in Big O context.

Question 9

procedure bubbleSort(sensorReadings)
  n <- length(sensorReadings)
  for i <- 1 to n - 1
    for j <- 1 to n - i
      if sensorReadings[j] > sensorReadings[j + 1]
        swap(sensorReadings[j], sensorReadings[j + 1])

procedure mergeSort(sensorReadings)
  if length(sensorReadings) <= 1
    return sensorReadings
  mid <- length(sensorReadings) / 2
  left <- mergeSort(sensorReadings[1..mid])
  right <- mergeSort(sensorReadings[mid+1..end])
  return merge(left, right)

1. Merge sort, because $O(n \log n)$ grows slower than $O(n^2)$ as input increases. (correct answer)
2. Bubble sort, because swapping adjacent values makes it $O(\log n)$ in practice.
3. Merge sort, because $O(n \log n)$ is the same as $O(n^2)$ when $n$ is large.
4. Bubble sort, because Big O ignores input limits and focuses on constant-time swaps.

Explanation: This question tests AP Computer Science Principles on algorithmic efficiency, specifically comparing quadratic and linearithmic sorting algorithms. Algorithmic efficiency refers to how effectively an algorithm performs in terms of time and space, often expressed using Big O notation to represent time complexity. In this passage, the comparison between bubble sort (O(n²)) and merge sort (O(n log n)) for sorting sensor readings that can spike to 100,000 items highlights how algorithm choice becomes critical for large, time-sensitive datasets. Choice A is correct because it accurately identifies merge sort as more efficient for large inputs, with O(n log n) growing much slower than O(n²) - for n=100,000, this means roughly 1.7 million operations versus 10 billion operations. This demonstrates understanding of how different growth rates impact real-world performance. Choice B is incorrect because it claims bubble sort's adjacent swapping makes it O(log n), which is false - the nested loops clearly show O(n²) behavior regardless of how swaps are performed. This error often occurs when students focus on implementation details rather than loop structure. To help students: Calculate actual operation counts for n=100,000 to show the dramatic difference. Explain that meeting time constraints often requires choosing algorithms with better asymptotic complexity. Watch for: students who think implementation tricks can change fundamental time complexity or who underestimate the impact of quadratic growth on large datasets.

Question 10

LINEAR_SEARCH(sortedList, target)
  FOR i <- 1 TO LENGTH(sortedList)
    IF sortedList[i] = target
      RETURN i
  RETURN -1

BINARY_SEARCH(sortedList, target)
  low <- 1
  high <- LENGTH(sortedList)
  WHILE low <= high
    mid <- (low + high) / 2
    IF sortedList[mid] = target
      RETURN mid
    ELSE IF sortedList[mid] < target
      low <- mid + 1
    ELSE
      high <- mid - 1
  RETURN -1

1. It guarantees a match exists, because it checks the middle element first.
2. It reduces checks by halving the remaining range each step, giving $O(\log n)$ time. (correct answer)
3. It works best on unsorted lists, because halving ignores element order.
4. It has $O(n)$ time but uses fewer comparisons than linear search for large $n$.

Explanation: This question tests AP Computer Science Principles on algorithmic efficiency, specifically understanding the fundamental advantage of binary search over linear search. Algorithmic efficiency refers to how effectively an algorithm performs in terms of time and space, often expressed using Big O notation to represent time complexity. In this passage, the comparison between linear search and binary search on sorted data shows how binary search achieves logarithmic O(log n) complexity by eliminating half the remaining elements with each comparison, while linear search maintains O(n) complexity. Choice B is correct because it accurately identifies the key mechanism - binary search reduces checks by halving the search space at each step, resulting in O(log n) time complexity, which means searching 1,000,000 scores requires only about 20 comparisons versus potentially 1,000,000. This demonstrates understanding of divide-and-conquer efficiency. Choice D is incorrect because it claims binary search has O(n) time complexity, which is false - the entire advantage of binary search is its O(log n) complexity. This error often occurs when students recognize binary search is better but misunderstand why, incorrectly attributing it to fewer comparisons within the same complexity class. To help students: Trace through binary search step-by-step showing the halving process. Calculate log₂ values for various list sizes to show dramatic savings. Watch for: confusion between 'fewer operations' and 'better complexity class' or misunderstanding that binary search requires sorted data.

Question 11

procedure linearSearch(sortedList, target)
  for index <- 1 to length(sortedList)
    if sortedList[index] = target
      return index
  return -1

procedure binarySearch(sortedList, target)
  low <- 1
  high <- length(sortedList)
  while low <= high
    mid <- (low + high) / 2
    if sortedList[mid] = target
      return mid
    else if sortedList[mid] < target
      low <- mid + 1
    else
      high <- mid - 1
  return -1

1. When the list is large and sorted, because $O(\log n)$ grows slower than $O(n)$. (correct answer)
2. When the list is unsorted, because binary search does not depend on ordering.
3. When the list is large, because linear search becomes $O(\log n)$ after enough queries.
4. When the target is missing, because binary search changes to $O(n)$ in the worst case.

Explanation: This question tests AP Computer Science Principles on algorithmic efficiency, specifically understanding when binary search provides advantages over linear search. Algorithmic efficiency refers to how effectively an algorithm performs in terms of time and space, often expressed using Big O notation to represent time complexity. In this passage, the comparison between linear search (O(n)) and binary search (O(log n)) on a sorted list of up to 2,000,000 ticket numbers highlights how logarithmic algorithms excel on large, sorted datasets. Choice A is correct because it accurately identifies that binary search outperforms linear search when the list is large and sorted, as O(log n) grows much slower than O(n) - for 2 million entries, binary search needs at most 21 comparisons versus potentially 2 million. This demonstrates understanding of both algorithm requirements and efficiency benefits. Choice B is incorrect because it claims binary search doesn't depend on ordering, when in fact binary search absolutely requires a sorted list to function correctly. This error often occurs when students memorize algorithm names without understanding their fundamental requirements. To help students: Emphasize that binary search's divide-and-conquer approach only works with sorted data. Show that log₂(2,000,000) ≈ 21, making the efficiency gain dramatic. Watch for: students who forget binary search's sorted list requirement or who don't appreciate the massive difference between O(n) and O(log n) at scale.

Question 12

LINEAR_SEARCH(sortedList, target)
  FOR i <- 1 TO LENGTH(sortedList)
    IF sortedList[i] = target
      RETURN i
  RETURN -1

BINARY_SEARCH(sortedList, target)
  low <- 1
  high <- LENGTH(sortedList)
  WHILE low <= high
    mid <- (low + high) / 2
    IF sortedList[mid] = target
      RETURN mid
    ELSE IF sortedList[mid] < target
      low <- mid + 1
    ELSE
      high <- mid - 1
  RETURN -1

1. When the list is sorted and large, because $O(\log n)$ grows much slower than $O(n)$. (correct answer)
2. When the list is unsorted, because binary search does not rely on element order.
3. When the target is missing, because linear search becomes $O(\log n)$ in that case.
4. When the list is small, because $O(n)$ is always worse than $O(2^n)$.

Explanation: This question tests AP Computer Science Principles on algorithmic efficiency, specifically understanding the conditions required for binary search to outperform linear search. Algorithmic efficiency refers to how effectively an algorithm performs in terms of time and space, often expressed using Big O notation to represent time complexity. In this passage, the comparison shows binary search with O(log n) complexity versus linear search with O(n) complexity, but binary search requires the list to be sorted to function correctly. Choice A is correct because it accurately identifies both conditions for binary search superiority: the list must be sorted (a prerequisite for binary search to work) and large (where the difference between O(log n) and O(n) becomes significant) - for 2,000,000 songs, binary search needs about 21 comparisons versus potentially 2,000,000. This demonstrates understanding of both algorithm requirements and scaling. Choice B is incorrect because it claims binary search works on unsorted lists, which is false - binary search's divide-and-conquer approach relies on sorted order to eliminate half the search space. This error often occurs when students focus only on complexity without understanding algorithm prerequisites. To help students: Demonstrate why binary search fails on unsorted data with examples. Show the dramatic difference in comparisons for large sorted lists. Watch for: forgetting that binary search requires sorted input or assuming all search algorithms work on any data.

Question 13

LINEAR_SEARCH(sortedList, target)
  FOR i <- 1 TO LENGTH(sortedList)
    IF sortedList[i] = target
      RETURN i
  RETURN -1

BINARY_SEARCH(sortedList, target)
  low <- 1
  high <- LENGTH(sortedList)
  WHILE low <= high
    mid <- (low + high) / 2
    IF sortedList[mid] = target
      RETURN mid
    ELSE IF sortedList[mid] < target
      low <- mid + 1
    ELSE
      high <- mid - 1
  RETURN -1

1. Binary search, because $O(\log n)$ grows more slowly than $O(n)$ as $n$ increases. (correct answer)
2. Linear search, because scanning avoids division and is therefore asymptotically faster.
3. Linear search, because the list is sorted and that makes $O(n)$ become $O(\log n)$.
4. Binary search, because it is $O(n)$ in the worst case on any list.

Explanation: This question tests AP Computer Science Principles on algorithmic efficiency, specifically understanding and comparing algorithm time complexities for search operations. Algorithmic efficiency refers to how effectively an algorithm performs in terms of time and space, often expressed using Big O notation to represent time complexity. In this passage, the comparison between linear search and binary search highlights how sorted data enables more efficient searching, with linear search having O(n) time complexity while binary search achieves O(log n) time complexity. Choice A is correct because it accurately identifies binary search as more efficient for large inputs, recognizing that O(log n) grows much more slowly than O(n) as the input size increases. This demonstrates understanding of logarithmic versus linear growth. Choice C is incorrect because it claims that being sorted makes linear search O(log n), which is false - linear search remains O(n) regardless of whether the list is sorted. This error often occurs when students confuse the prerequisites for binary search with its effect on linear search. To help students: Demonstrate with concrete numbers how log n grows (e.g., log₂(1,000,000) ≈ 20 versus 1,000,000 comparisons). Emphasize that binary search requires sorted data but linear search's complexity is unchanged by sorting. Watch for: students thinking sorting automatically improves any search algorithm or misunderstanding logarithmic growth.

Question 14

procedure fibRecursive(n)
  if n <= 1
    return n
  return fibRecursive(n - 1) + fibRecursive(n - 2)

procedure fibDP(n)
  if n <= 1
    return n
  fibValues[0] <- 0
  fibValues[1] <- 1
  for i <- 2 to n
    fibValues[i] <- fibValues[i - 1] + fibValues[i - 2]
  return fibValues[n]

1. Naive recursion, because $O(2^n)$ grows slowly until $n$ becomes very large.
2. Dynamic programming, because $O(n)$ increases much more slowly than $O(2^n)$. (correct answer)
3. Naive recursion, because it uses fewer variables and therefore has lower Big O time.
4. Dynamic programming, because its time complexity is $O(2^n)$ due to the loop.

Explanation: This question tests AP Computer Science Principles on algorithmic efficiency, specifically understanding exponential versus linear time complexity in recursive problems. Algorithmic efficiency refers to how effectively an algorithm performs in terms of time and space, often expressed using Big O notation to represent time complexity. In this passage, the comparison between naive recursive Fibonacci (O(2^n)) and dynamic programming Fibonacci (O(n)) highlights how memoization or iteration can dramatically reduce time complexity by avoiding redundant calculations. Choice B is correct because it accurately identifies dynamic programming as more efficient for large inputs, with O(n) growing much more slowly than O(2^n) - for n=40, this is the difference between about 40 operations versus over a trillion. This demonstrates understanding of exponential growth's severity. Choice A is incorrect because it claims O(2^n) grows slowly until n becomes very large, when in reality exponential growth becomes problematic even for moderate values like n=40. This error often occurs when students underestimate exponential growth rates. To help students: Calculate actual values - for n=40, 2^40 ≈ 1.1 trillion while 40 is just 40. Visualize the recursion tree to show repeated subproblems in naive approach. Watch for: students who don't grasp how quickly exponential functions grow or who think all recursive solutions are inefficient.

Question 15

DFS(graph, start)
  stack <- [start]
  visited <- EMPTY_SET
  WHILE stack NOT EMPTY
    node <- POP(stack)
    IF node NOT IN visited
      ADD node TO visited
      FOR each neighbor IN graph[node]
        PUSH neighbor ONTO stack

BFS(graph, start)
  queue <- [start]
  visited <- EMPTY_SET
  WHILE queue NOT EMPTY
    node <- DEQUEUE(queue)
    IF node NOT IN visited
      ADD node TO visited
      FOR each neighbor IN graph[node]
        ENQUEUE neighbor INTO queue

1. When the graph is large, because BFS has $O(\log V)$ time but DFS has $O(V+E)$.
2. When the target is near the start, because BFS checks closer layers before deeper paths. (correct answer)
3. Always, because BFS visits fewer vertices than DFS on any connected graph.
4. When roads are weighted, because BFS automatically finds the cheapest route.

Explanation: This question tests AP Computer Science Principles on algorithmic efficiency, specifically understanding when different graph traversal algorithms perform better despite having the same time complexity. Algorithmic efficiency refers to how effectively an algorithm performs in terms of time and space, often expressed using Big O notation to represent time complexity. In this passage, the comparison between DFS (Depth-First Search) and BFS (Breadth-First Search) shows both have O(V+E) time complexity, but their traversal patterns differ - DFS explores deeply before backtracking while BFS explores layer by layer. Choice B is correct because it accurately identifies that BFS outperforms DFS when the target is near the start, as BFS explores nodes in order of their distance from the start, checking all closer nodes before moving to deeper ones. This demonstrates understanding beyond just time complexity. Choice A is incorrect because it claims BFS has O(log V) time complexity, which is false - both algorithms have the same O(V+E) complexity. This error often occurs when students confuse binary search's logarithmic complexity with graph traversal algorithms. To help students: Use visual demonstrations showing how BFS explores outward in layers while DFS dives deep. Emphasize that same time complexity doesn't mean identical performance in all scenarios. Watch for: misconceptions that BFS is always faster or confusion between algorithm behavior and asymptotic complexity.

Question 16

DFS(graph, start)
  stack <- [start]
  visited <- EMPTY_SET
  WHILE stack NOT EMPTY
    node <- POP(stack)
    IF node NOT IN visited
      ADD node TO visited
      FOR each neighbor IN graph[node]
        PUSH neighbor ONTO stack

BFS(graph, start)
  queue <- [start]
  visited <- EMPTY_SET
  WHILE queue NOT EMPTY
    node <- DEQUEUE(queue)
    IF node NOT IN visited
      ADD node TO visited
      FOR each neighbor IN graph[node]
        ENQUEUE neighbor INTO queue

1. DFS, because stacks make the runtime $O(V)$ while BFS is $O(V+E)$.
2. BFS, because queues guarantee $O(E)$ while DFS is $O(V^2)$.
3. Neither; both are $O(V+E)$, so asymptotically they scale the same. (correct answer)
4. BFS, because it visits each vertex at most $\log V$ times.

Explanation: This question tests AP Computer Science Principles on algorithmic efficiency, specifically understanding that different algorithms can have the same time complexity. Algorithmic efficiency refers to how effectively an algorithm performs in terms of time and space, often expressed using Big O notation to represent time complexity. In this passage, both DFS (Depth-First Search) and BFS (Breadth-First Search) are shown to have O(V+E) time complexity, meaning they visit each vertex and edge once during a complete traversal. Choice C is correct because it accurately recognizes that both algorithms have the same O(V+E) time complexity, so asymptotically they scale identically with graph size - neither has a lower time complexity than the other. This demonstrates understanding that different algorithms can share the same complexity class. Choice A is incorrect because it claims DFS has O(V) complexity while BFS has O(V+E), which is false - both must potentially examine all vertices and edges, giving both O(V+E) complexity. This error often occurs when students focus on the data structure used (stack vs queue) rather than the traversal pattern. To help students: Emphasize that time complexity measures operations performed, not the data structure used. Show that both algorithms visit each vertex and edge exactly once in worst case. Watch for: assumptions that different data structures automatically mean different complexities.

Question 17

procedure fibRecursive(n)
  if n <= 1
    return n
  return fibRecursive(n - 1) + fibRecursive(n - 2)

procedure fibDP(n)
  if n <= 1
    return n
  prev <- 0
  curr <- 1
  for i <- 2 to n
    next <- prev + curr
    prev <- curr
    curr <- next
  return curr

1. It reduces repeated work, changing growth from $O(2^n)$ to $O(n)$. (correct answer)
2. It makes Fibonacci independent of n, so the runtime becomes $O(1)$.
3. It guarantees exact results only for large n, unlike recursion.
4. It sorts intermediate values, which is why it improves from $O(n^2)$ to $O(n)$.

Explanation: This question tests AP Computer Science Principles on algorithmic efficiency, specifically understanding how dynamic programming eliminates redundant computation. Algorithmic efficiency refers to how effectively an algorithm performs in terms of time and space, often expressed using Big O notation to represent time complexity. In this passage, the comparison shows how naive recursion recalculates the same Fibonacci values multiple times (leading to O(2^n) complexity), while dynamic programming stores and reuses previously calculated values (achieving O(n) complexity). Choice A is correct because it accurately identifies that dynamic programming reduces repeated work, changing growth from exponential O(2^n) to linear O(n) by storing intermediate results instead of recalculating them. This demonstrates understanding of memoization's impact on efficiency. Choice B is incorrect because it claims the runtime becomes O(1) (constant time), which would mean the algorithm takes the same time regardless of n - this is false as the loop still runs n times. This error often occurs when students confuse improved efficiency with constant-time operations. To help students: Draw the recursion tree for fib(5) showing repeated calculations, then show how DP calculates each value only once. Emphasize that O(n) is still dependent on n, just linearly rather than exponentially. Watch for: students who think any optimization makes algorithms constant-time or who don't understand how storing results prevents recalculation.