A Level Computer Science OCR Practice Exam

Which search algorithm has a time complexity of O(n)?

1. Linear Search

2. Binary Search

3. Hash Table Search

4. Graph Search

The correct answer is: Linear Search

The search algorithm with a time complexity of O(n) is linear search. This algorithm works by sequentially checking each element in a list or array until the desired value is found or the end of the structure is reached. Since this method requires examining potentially every element in the worst-case scenario, the time complexity is directly proportional to the number of elements in the data set, which is expressed as O(n). In contrast, binary search operates on sorted data structures and takes O(log n) time complexity since it repeatedly divides the search interval in half. Hash table searches typically have an average-case time complexity of O(1), depending on the implementation and hash function, while graph searches, such as breadth-first search or depth-first search, depend on both the number of vertices and edges, typically yielding a time complexity of O(V + E), where V is the number of vertices and E is the number of edges. Thus, linear search is distinctly characterized by its O(n) time complexity due to its straightforward approach of checking each element one by one.