Timeline for Randomized algorithm to make a Binary Search Tree from an array of $n$ distinct elements

7 events

when toggle format	what		by	license	comment
Sep 23, 2014 at 5:29	comment	added	dibyendu		@D.W. Sorry for replying late. I was in the middle of my semester exam. What I've tried is as follows: $$\lceil\log{_{2-\epsilon}n}\rceil = \left\lceil\frac{\log{_{2}n}}{\log{_{2}{(2-\epsilon)}}}\right\rceil=\left\lceil{\frac{\log{_{2}n}}{0.83}}\right\rceil=1.2\left\lceil\log_2n\right\rceil$$ So, it'll create a lop-sided tree with one branch $(1.2-1)\times100=20\%$ higher than the ideal height $i.e\ \log_2n$. Here is where I'm stuck. Does this $20\%$ signify that I've to choose the root element from the middle $20\%$ of the elements of $\mathcal{A}$ ?
Sep 17, 2014 at 16:11	comment	added	D.W.♦		OK, great, now your question is clearer. That's a good improvement. Thank you. That brings me to the next set of questions: What have you tried? What are your thoughts? Where did you get stuck? We want to help you with your specific problems, not solve your exercise for you. As it is we don't know what this problem is and thus how to help. See here for a relevant discussion.
Sep 17, 2014 at 16:09	history	edited	D.W.♦	CC BY-SA 3.0	Improve question.
Sep 17, 2014 at 9:18	history	edited	Raphael	CC BY-SA 3.0	edited tags
Sep 17, 2014 at 6:59	history	edited	dibyendu	CC BY-SA 3.0	Added example
Sep 16, 2014 at 22:45	review	Close votes
Sep 17, 2014 at 7:23
Sep 16, 2014 at 20:50	history	asked	dibyendu	CC BY-SA 3.0