Multiple choice

The worst case running time to search for an element in a balanced binary search tree with n2n elements is

  1. $\theta$(n log n)
  2. $\theta$(n2n)
  3. $\theta$(n)
  4. $\theta$(log n)
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

The worst case search time in a balanced BST on 'x' nodes is logx. So, if x = n2n, then log(n2n) = logn + log(2n) = logn + n = $\theta$(n)

Keep practicing — related questions