Searching and Sorting Algorithms Flashcards
6 cards from real AP CSA practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 6 Searching and Sorting Algorithms flashcards as text
What is the time complexity of linear search in the worst case?
Answer: O(n)
Linear search checks every element in the worst case (target not present), giving O(n) time complexity.
What precondition must be met before applying binary search to an array?
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.
What is the worst-case time complexity of binary search?
Answer: O(log n)
Binary search halves the search space each step, giving O(log n) comparisons in the worst case.
Which sorting algorithm repeatedly finds the minimum element and places it at the beginning?
Answer: Selection sort
Selection sort works by finding the smallest unsorted element and swapping it to its correct sorted position in each pass.
In bubble sort, what happens during each pass through the array?
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.
What is the worst-case time complexity of selection sort?
Answer: O(n²)
Selection sort has two nested loops — outer n iterations and inner up to n comparisons — giving O(n²) worst-case complexity.