13.3. One Dimensional Case

Try these first

1. 1.

   What is the time complexity of sorting n points?

   Hint

   Think of common sorting algorithms.

2. 2.

   Why do we only compare adjacent points in a sorted list for finding the closest pair?

   Hint

   Consider the implications of sorting.

3. 3.

   What is the overall time complexity of finding the closest pair of points in one dimension?

   • O(n²)
   • O(n log n)
   • O(n)

   Hint

   Focus on the sorting step.

4. 4.

   True or False: In a sorted list, the closest pair of points must be adjacent.

   • True
   • False

   Hint

   Think about the nature of sorting.

5. 5.

   You have five points at coordinates [10, 2, 4, 6, 8]. Detail the steps to find the closest pair.

   Hint

   What is the first step you need to take when dealing with a set of unsorted points?

6. 6.

   Explain why we assume distances may vary in a more complex scenario with larger datasets.

   Hint

   Consider how density might affect the closest points.