ACtE05 · Chapter 5Programming & Applications🏛️ Past Licensure QuestionID: 67c8b2c8
What is the average-case time complexity of searching for an element in an unsorted linear data structure (such as an array or linked list) containing elements?
What is the average-case time complexity of searching for an element in an unsorted linear data structure (such as an array or linked list) containing elements?
Multiple Choice Options
- A
O(1)
- B✓ Correct Option
O(n)
- C
O(log n)
- D
O(n^2)
Detailed Technical Solution & Explanation
In linear search across an unsorted collection of elements, the target element requires examining on average elements. In Big-O asymptotic notation, this is .
Option Analysis:
•
Option A (O(1)): Best-case time complexity (when target is at index 0) or hash table lookup, NOT average linear search.
•
Option B (O(n)): Correct. Linear search average time complexity is asymptotically linear .
•
Option C (O(log n)): Binary search on sorted arrays.
•
Option D (O(n^2)): Quadratic complexity, typical of nested pairwise comparisons.
Reference: Demo2 · Set 2NEC Licensure Syllabus