edited by
3,420 views

2 Answers

Best answer
72 votes
72 votes
The correct answer is option c, $\Theta(\sqrt{n})$.

$$\begin{align*}
​n &= 1 + 2 + 3 + \cdots + (h\,\color{red}{+1})\\[1em]
&= \frac{(h+1)(h+2)}{2}\\[1em]
2n &= h^2 + 3h + 2\\[1em]
0 &=  h^2 + 3h + (2 - 2n)\\[2em]
\hdashline
\implies h &= \frac{-3 \,\color{red}{+}\, \sqrt{3^2 - 4 \cdot (2 -2n)}}{2} & \because h\geq 0\\[2em]
&= \frac{-3 + \sqrt{8n+1}}{2}\\[1em]
\implies h &= \Theta(\sqrt n)
\end{align*}$$
edited by
–7 votes
–7 votes
Ans will be O(n/log n)

if we check for height ,

when,  n=3, height=3/log3=3/1.58=3/2=1

     n=6,   height=6/log6=6/2.58=6/3=2

     n=10,  height=10/log10=10/3.32=10/3=3.33=3

     n=15, height=15/log15=15/3.90=15/4=3.75=4

      n=21  height=21/log21=21/4.39=21/4=5

      n=28  height=28/log28=28/4.8=28/5=5.6=6

so if we further expand the tree only (d) will give correct answer
edited by
Answer:

Related questions

27 votes
27 votes
3 answers
3
makhdoom ghaya asked Nov 8, 2015
3,206 views
In a relational database there are three relations:$Customers = C\textsf{(CName)}$,$Shops = S \textsf{(SName)}$,$Buys = B\textsf{(CName, SName)}$.Which of the following r...