Expo binary search

Computer Science Level 2

What is the worst case running time for searching an element in a balanced binary search tree with $n \times 2^{n}$ elements?

\Theta(n\log n)

\Theta(\log(n))

\Theta(2^{n}\log(n))

\Theta(n)

\Theta(n\cdot 2^{n})

1 solution

Anoubhav Agarwaal
Aug 7, 2020

Searching for an element in a balanced binary search tree with m nodes has a time complexity of O(log m).

Here, m = n x 2^n. Substituting in O(log m), we have,

O(log (n x 2^n)) = O(log n + log 2^n) = O(log n + n * log 2) = O(log n + n) = O (n)

We use the key property of logarithms: log (a x b) = log a + log b