GATE 2012 CS (CS1) – Question 15

Algorithms · Asymptotic Analysis and Time/Space Complexity · 1 mark · Multiple choice

Find the worst-case search time in a balanced BST with $n2^n$ elements.

$\Theta(n\log n)$
$\Theta(n2^n)$
$\Theta(n)$
$\Theta(\log n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $\Theta(n)$

Explanation

A balanced BST search takes Θ(log N) for N elements. Here $\log(n2^n)=\log n+n\log2=\Theta(n)$. Thus option C. The exponential element count still produces only linear-in-n tree height.

More Asymptotic Analysis and Time/Space Complexity questions

GATE 2012 CS (CS1) Q28 – W(n) and A(n) are worst-case and average running times on inputs of size n. Which always…
GATE 2013 CS (CS1) Q40 – How many elements can heap sort sort in ( n) time?
GATE 2013 CS (CS1) Q41 – What is the asymptotic return value, rather than running time?
GATE 2011 CS (CS1) Q47 – Find increasing asymptotic growth order for f 1(n)=2n, f 2(n)=n3/2, f 3(n)=n 2n, f 4(n)=n…
GATE 2010 CS (CS1) Q22 – Packages A,B process n=10k database records. A needs 0.0001n² time; B needs 10n 10n. Find…
GATE 2015 CS (CS2) Q16 – An unordered list contains n distinct elements. How many comparisons are needed to find…

All Asymptotic Analysis and Time/Space Complexity questions →