MHB What is the time complexity of the binary search algorithm?

[I like Serena]

Will the resursion-tree be like that?

View attachment 3390

If so, for which value of $n$ will it end? And how can I find the last value that it will take? (Thinking)

It would help if you specify at each level the fraction of $n$. (Worried)

At the top level you are calculating for $T(n)$.
One level down for $T(\lfloor\frac n 2\rfloor)$.
Etcetera, until we get to $T(0)$ for which the cost is $2$.

To get a sense of this, perhaps we can pick an example for say $n=8$. (Mmm)
And perhaps another one for $n=11$.

 

[evinda]

It would help if you specify at each level the fraction of $n$. (Worried)

At the top level you are calculating for $T(n)$.
One level down for $T(\lfloor\frac n 2\rfloor)$.
Etcetera, until we get to $T(0)$ for which the cost is $2$.

To get a sense of this, perhaps we can pick an example for say $n=8$. (Mmm)
And perhaps another one for $n=11$.

I am confused now.. (Sweating)

It is:

$$T(8)=T(4)+10=(T(2)+10)+10=T(1)+30=T(0)+40=12$$

$$T(11)=T(5)+10=T(2)+20=T(1)+30=12$$

But, how can could we make the recursion-tree? (Thinking)

 

[I like Serena]

I am confused now.. (Sweating)

It is:

$$T(8)=T(4)+10=(T(2)+10)+10=T(1)+30=T(0)+40=12$$

$$T(11)=T(5)+10=T(2)+20=T(1)+30=12$$

But, how can could we make the recursion-tree? (Thinking)

Like this:
\begin{array}{|c|c|}
\hline
& \text{cost tree}\\
\hline
n=8 & 10 \\
& \downarrow \\
\lfloor n/2\rfloor =4 & 10 \\
& \downarrow \\
\lfloor \lfloor n/2\rfloor / 2\rfloor=\lfloor n/4\rfloor=2 & 10 \\
& \downarrow \\
\lfloor n/8\rfloor=1 & 10 \\
& \downarrow \\
\lfloor n/16\rfloor=0 & 2 \\
\hline
\text{Total }T(n) & 42 \\
\hline
\end{array}

How many times do we have $10$? (Wondering)

 

[evinda]

Like this:
\begin{array}{|c|c|}
\hline
& \text{cost tree}\\
\hline
n=8 & 10 \\
& \downarrow \\
\lfloor n/2\rfloor =4 & 10 \\
& \downarrow \\
\lfloor \lfloor n/2\rfloor / 2\rfloor=\lfloor n/4\rfloor=2 & 10 \\
& \downarrow \\
\lfloor n/8\rfloor=1 & 10 \\
& \downarrow \\
\lfloor n/16\rfloor=0 & 2 \\
\hline
\text{Total }T(n) & 42 \\
\hline
\end{array}

How many times do we have $10$? (Wondering)

$$\lfloor \frac{8}{2}\rfloor \text{ times, right? }$$

(Thinking)

 

[I like Serena]

$$\lfloor \frac{8}{2}\rfloor \text{ times, right? }$$

(Thinking)

Let's do it for $n=11$ as well:
\begin{array}{|c|c|}
\hline
& \text{cost tree}\\
\hline
n=11 & 10 \\
& \downarrow \\
\lfloor n/2\rfloor =5 & 10 \\
& \downarrow \\
\lfloor \lfloor n/2\rfloor / 2\rfloor=\lfloor n/4\rfloor=2 & 10 \\
& \downarrow \\
\lfloor n/8\rfloor=1 & 10 \\
& \downarrow \\
\lfloor n/16\rfloor=0 & 2 \\
\hline
\text{Total }T(n) & 42 \\
\hline
\end{array}

Is it $\lfloor \frac{11}{2}\rfloor$ times that we have $10$? (Wondering)

 

[evinda]

Let's do it for $n=11$ as well:
\begin{array}{|c|c|}
\hline
& \text{cost tree}\\
\hline
n=11 & 10 \\
& \downarrow \\
\lfloor n/2\rfloor =5 & 10 \\
& \downarrow \\
\lfloor \lfloor n/2\rfloor / 2\rfloor=\lfloor n/4\rfloor=2 & 10 \\
& \downarrow \\
\lfloor n/8\rfloor=1 & 10 \\
& \downarrow \\
\lfloor n/16\rfloor=0 & 2 \\
\hline
\text{Total }T(n) & 42 \\
\hline
\end{array}

Is it $\lfloor \frac{11}{2}\rfloor$ times that we have $10$? (Wondering)

No, we have $4$ times cost $10$, and not $5$. (Worried)

How could we find a general formula? (Thinking)

Is it maybe:

$$\sum_{i=0}^{i-1} 10+2$$

(Thinking)

 

[I like Serena]

No, we have $4$ times cost $10$, and not $5$. (Worried)

How could we find a general formula? (Thinking)

Is it maybe:

$$\sum_{i=0}^{i-1} 10+2$$

(Thinking)

That doesn't look like a proper formula!

Anyway, I'm off to sleep now. (Sleepy)