Algorithm Runtime Quiz: Test Your Knowledge of Big O Notation

📚 Quick Study Guide

• ⏱️ Big O notation describes the upper bound of an algorithm's runtime.
• 📈 It focuses on how the runtime grows as the input size increases.
• 🥇 Common complexities (fastest to slowest): $O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!)$
• 🧮 $O(1)$: Constant time - the runtime is independent of the input size.
• 🔎 $O(\log n)$: Logarithmic time - runtime increases logarithmically with input size (e.g., binary search).
• 🚶 $O(n)$: Linear time - runtime increases linearly with input size (e.g., a simple for loop).
• 🌳 $O(n \log n)$: Linearithmic time - often seen in efficient sorting algorithms (e.g., merge sort).
• 🧱 $O(n^2)$: Quadratic time - runtime increases quadratically with input size (e.g., nested for loops).
• 💣 $O(2^n)$: Exponential time - runtime doubles with each addition to the input dataset (e.g., brute force).
• 🤯 $O(n!)$: Factorial time - runtime grows extremely quickly (e.g., generating all permutations of a set).
• 💡 When analyzing code, focus on the dominant term (the one that grows the fastest).

🧪 Practice Quiz

1. What is the Big O notation for an algorithm that iterates through an array once?
   1. O(1)
   2. O(log n)
   3. O(n)
   4. O(n^2)
2. Which of the following Big O notations represents the fastest runtime?
   1. O(n)
   2. O(log n)
   3. O(n^2)
   4. O(2^n)
3. What is the Big O notation for binary search?
   1. O(n)
   2. O(n^2)
   3. O(log n)
   4. O(1)
4. An algorithm has nested loops, each iterating through the input of size n. What is its Big O notation?
   1. O(n)
   2. O(n log n)
   3. O(n^2)
   4. O(2n)
5. Which sorting algorithm typically has a time complexity of O(n log n)?
   1. Bubble Sort
   2. Insertion Sort
   3. Merge Sort
   4. Selection Sort
6. What is the Big O notation for accessing an element in an array by its index?
   1. O(n)
   2. O(log n)
   3. O(1)
   4. O(n log n)
7. What does Big O notation primarily describe?
   1. The exact runtime of an algorithm
   2. The memory usage of an algorithm
   3. The upper bound of an algorithm's runtime growth
   4. The lower bound of an algorithm's runtime growth