The worst case running time to search for an element in a balanced binary search tree with $n2^{n}$ elements is
The worst case running time to search for an element in a balanced binary search tree with n elements is log(n) because Balanced search tree have height logn
for n2^{n } elements replace n2^{n} in place of n
Θ(log(n2^{n})) =Θ(logn+log2^{n}) =Θ(logn+nlog2)
=Θ(logn+n) =Θ(n)
Gatecse