GATE CS 2012 Q.5 (CS Q.5): Binary Trees, Binary Search Trees and Balanced Trees

The worst case running time to search for an element in a balanced binary search tree with $n 2^n$ elements is

$\Theta(n \log n)$

$\Theta(n 2^n)$

$\Theta(n)$

$\Theta(\log n)$

Official answer and solution

Official answer: C
From: Official GATE 2012 answer key

Solution

Calculate the worst-case search time in a balanced binary search tree with N elements as Theta(log N).

In a balanced binary search tree (such as an AVL tree or Red-Black tree) containing $N$ elements, the height of the tree is bounded by $O(\log N)$ . Consequently, searching for an element takes worst-case time proportional to its height:

T(N) = \Theta(\log N)

Here, the number of elements is given as $N = n 2^n$ :

\log(N) = \log(n 2^n) = \log_2 n + \log_2(2^n) = \log_2 n + n

As $n \to \infty$ , the linear term $n$ dominates the logarithmic term $\log_2 n$ :

\Theta(\log_2 n + n) = \Theta(n)

Therefore, the worst-case running time to search for an element is $\Theta(n)$ , corresponding to option (C).

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2012 Computer Science and Information Technology (CS)
Question: 5 of 65, printed as CS Q.5
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source