Sorting Algorithms and Big O Notation Quiz for AP Computer Science A

📚 Quick Study Guide

• 🔍 Sorting Algorithms: These algorithms arrange elements in a specific order (e.g., ascending or descending). Common ones include Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quick Sort.
• ⏱️ Bubble Sort: Compares adjacent elements and swaps them if they are in the wrong order. Simple but inefficient for large datasets. Average and Worst-case time complexity: $O(n^2)$. Best-case time complexity: $O(n)$.
• 📍 Selection Sort: Finds the minimum element and places it at the beginning. Repeats for the remaining unsorted portion. Time complexity: $O(n^2)$ in all cases.
• ✏️ Insertion Sort: Builds the sorted array one element at a time by inserting elements into their correct position. Efficient for small datasets or nearly sorted data. Average and Worst-case time complexity: $O(n^2)$. Best-case time complexity: $O(n)$.
• ➗ Merge Sort: Divides the array into halves, recursively sorts them, and then merges the sorted halves. Efficient and stable. Time complexity: $O(n \log n)$ in all cases.
• ⚡ Quick Sort: Selects a 'pivot' element and partitions the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. Average time complexity: $O(n \log n)$. Worst-case time complexity: $O(n^2)$. Best-case time complexity: $O(n \log n)$.
• 📊 Big O Notation: Describes the upper bound of an algorithm's time or space complexity as the input size grows. It focuses on the dominant term and ignores constants.
• 📈 Common Big O Notations:
  • $O(1)$: Constant time
  • $O(\log n)$: Logarithmic time
  • $O(n)$: Linear time
  • $O(n \log n)$: Linearithmic time
  • $O(n^2)$: Quadratic time
  • $O(2^n)$: Exponential time
  • $O(n!)$: Factorial time

Practice Quiz

1. What is the time complexity of Bubble Sort in the worst-case scenario?
   1. $O(n)$
   2. $O(\log n)$
   3. $O(n^2)$
   4. $O(n \log n)$
2. Which sorting algorithm has a time complexity of $O(n \log n)$ in all cases?
   1. Quick Sort
   2. Insertion Sort
   3. Merge Sort
   4. Selection Sort
3. Which of the following Big O notations represents the fastest-growing function?
   1. $O(n)$
   2. $O(\log n)$
   3. $O(n^2)$
   4. $O(1)$
4. What is the best-case time complexity of Insertion Sort?
   1. $O(n)$
   2. $O(n^2)$
   3. $O(n \log n)$
   4. $O(1)$
5. Which sorting algorithm is generally considered the most efficient for large, randomly ordered datasets (on average)?
   1. Bubble Sort
   2. Selection Sort
   3. Quick Sort
   4. Insertion Sort
6. What is the time complexity of accessing an element in an array by its index?
   1. $O(n)$
   2. $O(\log n)$
   3. $O(n^2)$
   4. $O(1)$
7. Which sorting algorithm performs the best with nearly sorted data?
   1. Merge Sort
   2. Quick Sort
   3. Insertion Sort
   4. Selection Sort