AP CSA Searching and Sorting Algorithms 1 — Questions and Answers
Question 1: What is the time complexity of linear search in the worst case?
- O(n) (Correct answer)
- O(log n)
- O(n²)
- O(1)
Correct answer: O(n)
Linear search checks every element in the worst case (target not present), giving O(n) time complexity.
Question 2: What precondition must be met before applying binary search to an array?
- The array must be sorted (Correct answer)
- The array must have an even number of elements
- The array must contain unique elements
- The array must be of type int
Correct answer: The array must be sorted
Binary search requires the array to be sorted so it can correctly discard half the remaining elements at each step.
Question 3: What is the worst-case time complexity of binary search?
- O(log n) (Correct answer)
- O(n)
- O(n log n)
- O(1)
Correct answer: O(log n)
Binary search halves the search space each step, giving O(log n) comparisons in the worst case.
Question 4: Which sorting algorithm repeatedly finds the minimum element and places it at the beginning?
- Selection sort (Correct answer)
- Bubble sort
- Insertion sort
- Merge sort
Correct answer: Selection sort
Selection sort works by finding the smallest unsorted element and swapping it to its correct sorted position in each pass.
Question 5: In bubble sort, what happens during each pass through the array?
- Adjacent elements are compared and swapped if out of order (Correct answer)
- The minimum element is found and moved to the front
- Elements are inserted into their correct position
- The array is divided in half
Correct answer: Adjacent elements are compared and swapped if out of order
Bubble sort compares adjacent pairs and swaps them if they are out of order, causing larger elements to 'bubble up' to the end.
Question 6: What is the worst-case time complexity of selection sort?
- O(n²) (Correct answer)
- O(n)
- O(log n)
- O(n log n)
Correct answer: O(n²)
Selection sort has two nested loops — outer n iterations and inner up to n comparisons — giving O(n²) worst-case complexity.
AP CSA Searching and Sorting Algorithms 1
What is the time complexity of linear search in the worst case?