In algorithm analysis using Big O notation, which option correctly matches common data structures with their typical average case time complexities for basic operations?

Introduction / Context:
This question assesses your understanding of Big O notation and how it applies to common data structures such as arrays, balanced binary search trees, and hash tables. Big O notation describes how the running time or space usage of an algorithm grows with the size of the input. Being able to estimate time complexities for basic operations is a fundamental skill in computer science and a key topic in technical interviews.

Given Data / Assumptions:

- We consider standard, typical implementations of these data structures, not worst possible adversarial cases unless stated.
- Arrays are contiguous blocks of memory where elements are accessible by index.
- Balanced binary search trees such as AVL trees or red black trees maintain logarithmic height.
- Hash tables use a good hash function and suitable collision resolution, giving O(1) average time for search and insertion under typical assumptions.

Concept / Approach:
Accessing an array element by index is O(1) time because computing the address involves a simple arithmetic formula and one memory access. Searching for an element in an unsorted array by scanning from beginning to end is O(n) in the average and worst case, because on average you may need to examine half of the elements and in the worst case all of them. In a balanced binary search tree, search complexity is O(log n) because the tree height is proportional to log n and each comparison moves down one level. In a well designed hash table, search, insertion, and deletion can be O(1) on average due to constant time computation of hash functions and near constant chain or bucket sizes.

Step-by-Step Solution:
Step 1: Analyze array index access. Given an array of n elements, computing arr[i] requires one offset calculation and one memory read regardless of n, which is O(1). Step 2: Analyze search in an unsorted array using linear scan. You may need to check each element until you find the target or reach the end, giving O(n) time complexity. Step 3: Consider a balanced binary search tree. Each comparison either finds the target or reduces the remaining search space approximately in half, which leads to a logarithmic number of steps and O(log n) time. Step 4: For a hash table with a good distribution, operations involve computing a hash code and then looking through a small bucket or chain, which on average does not grow significantly with n, leading to O(1) average time. Step 5: Option A lists these well known complexities precisely, matching standard algorithm analysis taught in data structures courses.

Verification / Alternative check:
You can verify these complexities by reviewing any standard algorithms textbook or by reasoning about how the number of operations grows with input size. For instance, doubling the array size does not change the time to access arr[i], but it roughly doubles the time to scan the whole array. Balanced search trees have height that grows like log base 2 of n, so adding many elements only raises the number of levels slowly. Hash tables rely on good hash functions and load factors to keep average bucket sizes bounded, preserving constant time behavior for typical workloads.

Why Other Options Are Wrong:
Option B incorrectly states that array index access is O(n), which ignores the constant time address calculation. It also assigns unrealistic complexities like O(n^2) and O(n^3) to standard search operations that are much faster in typical implementations. Option C mislabels complexities by claiming tree search is O(1) and unsorted array search is O(log n), which are not accurate for the usual algorithms. Option D is clearly wrong because different data structures and operations have different time behaviors; otherwise there would be little reason to choose between them.

Common Pitfalls:
Common mistakes include confusing average case and worst case complexities, misremembering the advantage of balanced trees over simple lists, and overlooking that hash tables rely on good hashing and load factor control to achieve O(1) average performance. Another pitfall is focusing only on time complexity and ignoring factors like constant factors, memory usage, and cache behavior. Nonetheless, Big O notation is an essential tool for reasoning about algorithm efficiency and choosing appropriate data structures in both interviews and production systems.

Final Answer:
The correct matching is that indexed access in an array is O(1), search in an unsorted array is O(n), search in a balanced binary search tree is O(log n), and search in a well implemented hash table is O(1) on average.