Data Structures, unit: Searching and Complexity Analysis. Core concepts, terminology, and worked-example cues a college student meets for this unit, building on prior units without repeating them. Front: a term, concept, or short problem cue. Back: the definition, explanation, or answer.
38 cards · basic cards · AI-written, checked twice. Edit anything.
- What is a search algorithm?
Show answer
An algorithm for finding a specific element or condition within a data structure- What is linear search?
Show answer
Checking each element in sequence until the target is found or the list ends- What is the time complexity of linear search?
Show answer
O(n)- What is binary search?
Show answer
Repeatedly halving a sorted list's search range by comparing the middle element to the target- What is the time complexity of binary search?
Show answer
O(log n)- What precondition must be true for binary search to work correctly?
Show answer
The data must already be sorted- What is Big O notation used for?
Show answer
Describing the upper bound of an algorithm's time or space complexity as input size grows- What does O(1) time complexity mean?
Show answer
Constant time, unaffected by input size- What does O(n) time complexity mean?
Show answer
Linear time, growing proportionally with input size- What does O(n^2) time complexity mean?
Show answer
Quadratic time, common in algorithms with nested loops over the input- What does O(log n) time complexity mean?
Show answer
Logarithmic time, where the problem size is repeatedly halved- What does O(n log n) time complexity mean?
Show answer
Linearithmic time, typical of efficient comparison-based sorting algorithms- What is best-case complexity?
Show answer
The minimum time or space an algorithm requires, under the most favorable input- What is worst-case complexity?
Show answer
The maximum time or space an algorithm requires, under the least favorable input- What is average-case complexity?
Show answer
The expected time or space an algorithm requires, averaged over typical inputs
FlashKeepers