What is the time complexity of the binary search algorithm?

[evinda]

Hello! (Wave)

    Index BinarySearch(Type A[1...N], Type value, Index low, Index high){
    1.  Index mid;
    2.  if (high<low) 
    3.      return -1
    4.  mid=low+(high-low)/2;
    5.  if (A[mid]>value) 
    6.      return  BinarySearch(A, value, low,mid-1);
    7.  else if (A[mid]<value) 
    8.      return  BinarySearch(A, value, mid+1,high);
    9.  else 
    10.      return mid
    }

Given the above algorithm, I want to calculate the time complexity.. (Thinking) The cost of the line $2$ is $1$.

The cost of the line $3$ is $1$.

The cost of the line $4$ is $4$.

The cost of the line $5$ is $2$.

The cost of the line $6$ is $T(\lfloor{\frac{n}{2} \rfloor})+1$.

The cost of the line $7$ is $2$.

The cost of the line $8$ is $T(\lfloor{\frac{n}{2} \rfloor})+1$.

The cost of the line $10$ is $1$.

But.. how can I find now the recurrence relation, that describes the time complexity? (Worried) (Thinking)

 

[Nono713]

Hello! (Wave)

    Index BinarySearch(Type A[1...N], Type value, Index low, Index high){
    1.  Index mid;
    2.  if (high<low) 
    3.      return -1
    4.  mid=low+(high-low)/2;
    5.  if (A[mid]>value) 
    6.      return  BinarySearch(A, value, low,mid-1);
    7.  else if (A[mid]<value) 
    8.      return  BinarySearch(A, value, mid+1,high);
    9.  else 
    10.      return mid
    }

Given the above algorithm, I want to calculate the time complexity.. (Thinking) The cost of the line $2$ is $1$.

The cost of the line $3$ is $1$.

The cost of the line $4$ is $4$.

The cost of the line $5$ is $2$.

The cost of the line $6$ is $T(\lfloor{\frac{n}{2} \rfloor})+1$.

The cost of the line $7$ is $2$.

The cost of the line $8$ is $T(\lfloor{\frac{n}{2} \rfloor})+1$.

The cost of the line $10$ is $1$.

But.. how can I find now the recurrence relation, that describes the time complexity? (Worried) (Thinking)

Observe that you recurse at most once, since it's an if/else condition. So in the worst case, you have:

$$T(n) = T(\frac{n}{2}) + C$$

where $C$ consists of all the constant time operations, we will aggregate them into a single constant for simplicity. Solving this for $T$ yields:

$$T(n) = \log_2(n) + k$$

for some constant $k$. Thus, in the worst case:

$$T(n) \in O(\log{n})$$

If you are asking for a rigorous way to go from the recurrence relation to its closed form solution, you may be interested in finding a proof of the Master theorem - Wikipedia, the free encyclopedia.

 

[I like Serena]

Hey! (Mmm)

Typically, your algorithm will be used with:

i = BinarySearch(A, value, 1, N)

Now suppose your algorithm is called with $N=0$.
What is the time complexity then? (Wondering)

And what if $N=1$? (Wondering)

 

[evinda]

Hey! (Mmm)

Typically, your algorithm will be used with:

i = BinarySearch(A, value, 1, N)

Now suppose your algorithm is called with $N=0$.
What is the time complexity then? (Wondering)

And what if $N=1$? (Wondering)

For $N=0$, we count the cost of the lines $2$ and $3$. So, the time complexity for this value of $N$ is $1+1=2$.

For $N=1$, we count the cost of the lines $2, 4, 5, 7, 9, 10$. So, the time complexity, in this case, is $1+4+2+2+0+1=10$.

Right? (Thinking)

 

[I like Serena]

For $N=0$, we count the cost of the lines $2$ and $3$. So, the time complexity for this value of $N$ is $1+1=2$.

Yep! (Nod)

For $N=1$, we count the cost of the lines $2, 4, 5, 7, 9, 10$. So, the time complexity, in this case, is $1+4+2+2+0+1=10$.

Right? (Thinking)

Not quite.
Time complexity (usually) means the worst case cost. (Sweating)

It appears you have made the assumption that value is in the array.
But that is not necessarily the case.

Suppose value is smaller than the single value that is in the array.
What is the cost then? (Wondering)

And suppose value is greater than the value in the array.
What would be the cost? (Wondering)

 

[evinda]

Not quite.
Time complexity (usually) means the worst case cost. (Sweating)

It appears you have made the assumption that value is in the array.
But that is not necessarily the case.

Suppose value is smaller than the single value that is in the array.
What is the cost then? (Wondering)

And suppose value is greater than the value in the array.
What would be the cost? (Wondering)

For $N=1$, we count the cost of the lines:

• $2, 4, 5, 6$
• $2, 4, 5, 7, 8$
• $2, 4, 5, 7, 10$

So, the time complexity in each case is:

• $1+4+2+T \left (\lfloor \frac{n}{2} \rfloor \right )+1=T \left (\lfloor \frac{n}{2} \rfloor \right )+8$
  
• $1+4+2+2+T \left (\lfloor \frac{n}{2} \rfloor \right )+1=T \left (\lfloor \frac{n}{2} \rfloor \right )+10$
  
• $1+4+2+2+1=10$

Or am I wrong? (Thinking)

 

[I like Serena]

For $N=1$, we count the cost of the lines:

• $2, 4, 5, 6$
• $2, 4, 5, 7, 8$
• $2, 4, 5, 7, 10$

So, the time complexity in each case is:

• $1+4+2+T \left (\lfloor \frac{n}{2} \rfloor \right )+1=T \left (\lfloor \frac{n}{2} \rfloor \right )+8$
  
• $1+4+2+2+T \left (\lfloor \frac{n}{2} \rfloor \right )+1=T \left (\lfloor \frac{n}{2} \rfloor \right )+10$
  
• $1+4+2+2+1=10$

Or am I wrong? (Thinking)

Yep.
That is correct! (Happy)

So which one is the most expensive?
Because that will be the time complexity.

Oh, and what is $n$? (Wondering)

 

[evinda]

So which one is the most expensive?
Because that will be the time complexity.

The cost that we find at the second case is the most expensive, right? (Thinking)
So, is the time complexity equal to $T(N)=T\left(\lfloor \frac{N}{2} \rfloor\right )+10$ ? Or is it only the time complexity, when $N=1$ ? (Thinking)

Oh, and what is $n$? (Wondering)

I wanted to write $N$, instead of $n$.. (Blush)

 

[I like Serena]

The cost that we find at the second case is the most expensive, right? (Thinking)
So, is the time complexity equal to $T(N)=T\left(\lfloor \frac{N}{2} \rfloor\right )+10$ ? Or is it only the time complexity, when $N=1$ ? (Thinking)

Good! (Nod)
We have verified this for $N=1$ now.

I wanted to write $N$, instead of $n$.. (Blush)

Good!
And actually, there's a little more to it... (Malthe)

Let's take a look at:

i = BinarySearch(A, value, 3, 4)

What is the time complexity?

And what is $n$ in this case? (Wondering)

 

[evinda]

Good!
And actually, there's a little more to it... (Malthe)

What do you mean? (Wasntme) What does $n$ represent? (Thinking)

Let's take a look at:

i = BinarySearch(A, value, 3, 4)

What is the time complexity?

I found the same as for $N=1$:

• $2, 4, 5, 6$
• $2, 4, 5, 7, 8$
• $2, 4, 5, 7, 10$

So, the time complexity in each case is:

• $1+4+2+T \left (\lfloor \frac{N}{2} \rfloor \right )+1=T \left (\lfloor \frac{N}{2} \rfloor \right )+8$
  
• $1+4+2+2+T \left (\lfloor \frac{N}{2} \rfloor \right )+1=T \left (\lfloor \frac{N}{2} \rfloor \right )+10$
  
• $1+4+2+2+1=10$

Is it right? (Thinking)

And what is $n$ in this case? (Wondering)

I don't know... (Blush) What could it be? (Worried)

 

[I like Serena]

What do you mean? (Wasntme) What does $n$ represent? (Thinking)

$n$ represents the number of elements that we're searching through.
It is only equal to $N$ in the first recursion.

I found the same as for $N=1$:

Is it right? (Thinking)

How can it be?
How can

i = BinarySearch(A, value, 1, 1)

have the same complexity as

i = BinarySearch(A, value, 3, 4)

In the latter case, there are 2 elements to search through instead of 1. (Doh)

I don't know... (Blush) What could it be? (Worried)

The number of elements to search through in a specific recursion. (Nerd)

 

[evinda]

How can it be?
How can

i = BinarySearch(A, value, 1, 1)

have the same complexity as

i = BinarySearch(A, value, 3, 4)

In the latter case, there are 2 elements to search through instead of 1. (Doh)

Isn't the complexity of

BinarySearch(A, value, 1, 1)

equal to $T(0)+10$ and of

BinarySearch(A, value, 3, 4)

$T(1)+10$ ? (Thinking)

Or am I wrong? (Worried)

 

[I like Serena]

Isn't the complexity of

BinarySearch(A, value, 1, 1)

equal to $T(0)+10$ and of

BinarySearch(A, value, 3, 4)

$T(1)+10$ ? (Thinking)

Or am I wrong? (Worried)

Yes! (Smile)
That is correct.

So what is the general complexity? (Wondering)

 

[evinda]

Yes! (Smile)
That is correct.

So what is the general complexity? (Wondering)

Is it : $T(n)=T \left ( \lfloor \frac{n}{2} \rfloor \right )+10$ ? (Thinking)

 

[I like Serena]

Is it : $T(n)=T \left ( \lfloor \frac{n}{2} \rfloor \right )+10$ ? (Thinking)

Yes... but this is incomplete... (Worried)

 

[evinda]

Yes... but this is incomplete... (Worried)

We should mention the initial value $T(0)=2$, right? (Thinking)

How could we explain formally that this is the general complexity? (Worried)

 

[I like Serena]

We should mention the initial value $T(0)=2$, right? (Thinking)

How could we explain formally that this is the general complexity? (Worried)

Count the cost for

i = BinarySearch(A, value, low, high)

where $\colorbox{lightgray}{low} = \colorbox{lightgray}{high}$.
This represents the case where $n=0$.

Count the worst case cost for

i = BinarySearch(A, value, low, high)

where $n=\colorbox{lightgray}{high} - \colorbox{lightgray}{low} + 1$.
This represents the general case for $n$.

Together they give you the recurrence relation for the time complexity. (Mmm)

The last step, that we should still take, is to solve the recurrence relation, and find a general formula for the time complexity. (Thinking)

 

[evinda]

Count the cost for

i = BinarySearch(A, value, low, high)

where $\colorbox{lightgray}{low} = \colorbox{lightgray}{high}$.
This represents the case where $n=0$.

Why is it $n=0$, when we are looking for the initial condition? (Worried)
Don't we have then one element? Or am I wrong? (Thinking)

 

[I like Serena]

Why is it $n=0$, when we are looking for the initial condition? (Worried)
Don't we have then one element? Or am I wrong? (Thinking)

You're right. (Blush)
Pick $\colorbox{lightgray}{high} = \colorbox{lightgray}{low} - 1$ instead.

 

[evinda]

You're right. (Blush)
Pick $\colorbox{lightgray}{high} = \colorbox{lightgray}{low} - 1$ instead.

A ok! So, can I formulate it like that? (Thinking)

The cost of the line $2$ is $1$.

The cost of the line $3$ is $1$.

The cost of the line $4$ is $4$.

The cost of the line $5$ is $2$.

The cost of the line $6$ is $T(\lfloor{\frac{n}{2} \rfloor})+1$.

The cost of the line $7$ is $2$.

The cost of the line $8$ is $T(\lfloor{\frac{n}{2} \rfloor})+1$.

The cost of the line $10$ is $1$.

When high=low-1, we count the cost of the following lines:
$$2,3$$
So, the time complexity is $2$ in this case.

In this case, the array has $0$ elements, so $T(0)=2$.

When $n=high-low+1$, we count the cost of the following lines:

• $2, 4, 5, 6$
• $2, 4, 5, 7, 8$
• $2, 4, 5, 7, 10$

So, the time complexity in each case is:

• $1+4+2+T \left (\lfloor \frac{n}{2} \rfloor \right )+1=T \left (\lfloor \frac{n}{2} \rfloor \right )+8$
  
• $1+4+2+2+T \left (\lfloor \frac{n}{2} \rfloor \right )+1=T \left (\lfloor \frac{n}{2} \rfloor \right )+10$
  
• $1+4+2+2+1=10$

So, in the worst case, the time complexity is: $$T(n)=T \left (\lfloor \frac{n}{2} \rfloor \right )+10$$

So, the recursive relation is:

$$T(n)=\left\{\begin{matrix}
T \left (\lfloor \frac{n}{2} \rfloor \right )+10 ,& n \geq 1 \\
2 , & n=0
\end{matrix}\right.$$

 

[I like Serena]

Yep.
That looks good! (Nod)

How about solving the recurrence relation? (Wondering)

 

[evinda]

Yep.
That looks good! (Nod)

How about solving the recurrence relation? (Wondering)

I will solve it! (Wait)

I have also an other question.. when we have something like that:

if ((A[mid]<value) and (low<=high)), do we have to count also a cost from the operator "and" or is the cost equal to $4$ ? (Thinking)

 

[I like Serena]

I will solve it! (Wait)

I have also an other question.. when we have something like that:

if ((A[mid]<value) and (low<=high)), do we have to count also a cost from the operator "and" or is the cost equal to $4$ ? (Thinking)

That's a bit arbitrary.

On the one hand it's an extra operation, and apparently every operation is counted as $1$, making the cost $4$.
Actually, I suspect this is intended. (Nod)

But on the other hand, it can also be written as the equivalent code:

if (A[mid]<value)
    if (low<=high)

in which case the cost is either $2$ or $3$, depending on which path is chosen. (Wasntme)

 

[evinda]

That's a bit arbitrary.

On the one hand it's an extra operation, and apparently every operation is counted as $1$, making the cost $4$.
Actually, I suspect this is intended. (Nod)

But on the other hand, it can also be written as the equivalent code:

if (A[mid]<value)
    if (low<=high)

in which case the cost is either $2$ or $3$, depending on which path is chosen. (Wasntme)

According to my notes, the elementary commands are:

Enter a value to a variable
Call of a method
Execution of an arithmetic operation
Comparison of two numbers
Indexing an array
Access of the memory adress, at which a pointer shows
Return of a method

So, should I count it? (Thinking)Also, is it the same to say that the time complexity is $x$ as to say that we have $x$ elementary commands in a line? For example, at the line $6$, do we have $T \left (\lfloor \frac{n}{2} \rfloor \right )+1$ elementary commands? (Thinking)

 

[I like Serena]

According to my notes, the elementary commands are:

Enter a value to a variable
Call of a method
Execution of an arithmetic operation
Comparison of two numbers
Indexing an array
Access of the memory adress, at which a pointer shows
Return of a method

So, should I count it? (Thinking)

Well, execution of a logical operation is not in the list.
So I guess that means that you shouldn't count it.

Also, is it the same to say that the time complexity is $x$ as to say that we have $x$ elementary commands in a line? For example, at the line $6$, do we have $T \left (\lfloor \frac{n}{2} \rfloor \right )+1$ elementary commands? (Thinking)

Yes. (Nod)

Or more accurately, in a worst case scenario where we assume that the input is such that the number of elementary commands is as high as possible. (Nerd)

 

[evinda]

Well, execution of a logical operation is not in the list.
So I guess that means that you shouldn't count it.

Yes. (Nod)

Or more accurately, in a worst case scenario where we assume that the input is such that the number of elementary commands is as high as possible. (Nerd)

A ok! If the array would be of the form $A[1 \dots n]$, would we have to take an other parameter for the recurrence relation, for example $N$ , where $N$ is the dimension of the part of the array, that we are lookig at? (Thinking)

 

[I like Serena]

A ok! If the array would be of the form $A[1 \dots n]$, would we have to take an other parameter for the recurrence relation, for example $N$ , where $N$ is the dimension of the part of the array, that we are lookig at? (Thinking)

Yes.
But let's do it the other way around.
Let's have an array of the form $A[1 \dots N]$ and look at a section of it with size $n$.
That way it fits with your problem statement. (Wink)

 

[evinda]

How about solving the recurrence relation? (Wondering)

What's the best way to solve the recurrence relation? Should I use a recursion-tree ? (Thinking)

 

[I like Serena]

What's the best way to solve the recurrence relation? Should I use a recursion-tree ? (Thinking)

Sounds good! (Smile)

 

[evinda]

Sounds good! (Smile)

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)

 

[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)