Question

The complexity of searching a balanced binary search tree with n nodes is in the order of group of answer choices

a) o(n)
b) o(n*n)
c) o(lg n)
d) o(1)

Answer 1

The complexity of searching a balanced binary search tree with n nodes is in the order of log n. The time complexity is determined by the height of the tree, which is typically log n. option c) o(log n).

Step-by-step explanation:

The complexity of searching a balanced binary search tree with n nodes is in the order of log n. The time complexity of searching a balanced binary search tree is determined by the height of the tree, which is typically log n where n is the number of nodes. This is because at each level of the tree, the number of nodes is approximately halved.

For example, if you have a balanced binary search tree with 16 nodes, the height of the tree will be approximately log2(16) = 4. This means that the search operation will take at most 4 steps to locate a desired node.

Therefore, the correct answer is option c) o(log n).