The worst case running time to search for an element in a balanced binary…
2012
The worst case running time to search for an element in a balanced binary search tree with \(n2^n\) elements is
- A.
\(Θ (n \ log \ n)\) - B.
\(Θ (n2^n)\) - C.
\(Θ (n)\) - D.
\(Θ (log \ n)\)
Attempted by 399 students.
Show answer & explanation
Correct answer: C
Key insight: the worst-case search time in a balanced binary search tree is proportional to the tree height, which is Θ(log N) for N nodes.
Let N = n·2^n (the given number of elements).
Height of the balanced BST = Θ(log N) = Θ(log(n·2^n)).
Compute the logarithm: log(n·2^n) = log n + log(2^n) = log n + n·log 2 = n + log n = Θ(n).
Therefore the worst-case running time to search for an element is Θ(n).
A video solution is available for this question — log in and enroll to watch it.