Question

Search complexity of a BST versus a linked list and sorted array.

a) BST: O(log n), Linked list: O(n), Sorted array: O(log n)
b) BST: O(n), Linked list: O(log n), Sorted array: O(n)
c) BST: O(log n), Linked list: O(log n), Sorted array: O(n)
d) BST: O(n), Linked list: O(n), Sorted array: O(log n)

Answer 1

The search complexities for a balanced Binary Search Tree (BST), a linked list, and a sorted array are O(log n), O(n), and O(log n), respectively. The correct option is a) BST: O(log n), Linked list: O(n), Sorted array: O(log n).

Step-by-step explanation:

The search complexity for a Binary Search Tree (BST), a linked list, and a sorted array varies based on the data structure and the state of the data contained within it.

For a BST, the average search complexity is O(log n) assuming that the tree is balanced. If the tree is not balanced and takes on a linear form, the worst-case search complexity is O(n). In the case of a linked list, the search complexity is O(n) because you have to potentially traverse the entire list to find the element. Lastly, a sorted array allows for binary search, which has a search complexity of O(log n). Therefore, the correct option that lists these complexities is:

a) BST: O(log n), Linked list: O(n), Sorted array: O(log n)