Algorithmic Efficiency · AP Computer Science Principles

AP Computer Science Principles Quiz

17 questions · no time limit

0:00

ALGORITHMS AND PROGRAMMING

Question 1 of 17

No time limit

Current

Answered

Flagged

Not seen

A school app must sort scoreList of up to 200,000 integers in under 2 seconds. Two options are tested: Pseudocode (Bubble Sort):

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])

Time complexity:

O(n^2)

. Pseudocode (Merge Sort):

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)

Time complexity:

O(n \log n)

. Based on the algorithms described, which algorithm has a lower time complexity for large inputs?

YOUR PROGRESS

QUESTIONS

Ready when you are

Answer in any order. Your progress shows here as you go.

QUESTIONS

KEYBOARD

Pick an answer ABCD

Next question ↵→

Flag for review F