Big O Notation for Sorting Algorithms Explained with Examples

📚 Quick Study Guide

• ⏱️ Big O notation describes the worst-case time complexity of an algorithm.
• 📈 It focuses on how the runtime or space requirements grow as the input size increases.
• 🔢 Common Big O complexities (from best to worst):
  • O(1): Constant time - execution time is independent of the input size.
  • O(log n): Logarithmic time - execution time increases logarithmically with the input size.
  • O(n): Linear time - execution time increases linearly with the input size.
  • O(n log n): Linearithmic time - execution time is a bit worse than linear.
  • O(n²): Quadratic time - execution time increases quadratically with the input size.
  • O(2ⁿ): Exponential time - execution time doubles with each addition to the input data set.
  • O(n!): Factorial time - execution time grows extremely rapidly.
• 🔎 Examples for sorting algorithms:
  • Bubble Sort: O(n²)
  • Insertion Sort: O(n²)
  • Selection Sort: O(n²)
  • Merge Sort: O(n log n)
  • Quick Sort: O(n log n) average, O(n²) worst case

Practice Quiz

1. What does Big O notation primarily describe?
   1. The exact runtime of an algorithm in seconds.
   2. The amount of memory an algorithm uses.
   3. The worst-case time complexity of an algorithm.
   4. The best-case time complexity of an algorithm.
2. Which of the following Big O notations represents the fastest time complexity?
   1. O(n)
   2. O(log n)
   3. O(n²)
   4. O(n log n)
3. What is the Big O complexity of Bubble Sort in the worst case?
   1. O(n)
   2. O(n log n)
   3. O(n²)
   4. O(1)
4. Which sorting algorithm has an average time complexity of O(n log n)?
   1. Insertion Sort
   2. Selection Sort
   3. Merge Sort
   4. Bubble Sort
5. What is the meaning of O(1) Big O notation?
   1. The algorithm takes constant time, regardless of input size.
   2. The algorithm takes a single second to run.
   3. The algorithm's runtime increases linearly with input size.
   4. The algorithm is always the best choice.
6. In Big O notation, what does 'n' typically represent?
   1. The number of operations performed by the algorithm.
   2. The size of the input data.
   3. The speed of the computer running the algorithm.
   4. The number of lines of code in the algorithm.
7. Which sorting algorithm has a worst-case time complexity of O(n²) but an average time complexity of O(n log n)?
   1. Merge Sort
   2. Quick Sort
   3. Heap Sort
   4. Insertion Sort