Xavier Holt edited We_take_textbf_Step_1__.tex  about 8 years ago

Commit id: d805d1bee7e9a4a8ccbe3b94952f6322d4ea67bf

deletions | additions      

       

It's trivial to see that after `unravelling' our recursive formula $i$ times we retrieve the following:  \begin{align*}  R\left(n\right):&= O\left(n\right) + 2R\left(\frac{n}{2}\right)\\  &= iO\left(n\right) + 2^iR\left(\frac{n}{2^i}\right) \end{align*}  When our point set contains one point, it's clear that $R\left(1\right)$ requires a constant amount of work. This occurs when $\frac{n}{2^i}=1$ or equivalently $i=\log_2 n$. We substitute this value into our equation above.