Searching an unsorted list by checking each item one by one is…
Options
- O(1), since each item is checked once
- O(log n), by halving the list
- O(n): linear search (Correct option)
- O(n²), by comparing every pair
Answer
O(n): linear search
Why
Linear search starts at the first item and compares each one until it finds the target or reaches the end. In the worst case it looks at all n items: O(n).
If the list were sorted you could use binary search (O(log n)); if you need many lookups, put the items in a set (O(1)).
Remember
Check every item = O(n).