Binary search math, log base 2 (n) issues

[ducmod]

Homework Statement

Hello!
Binary search requires O( log2(n) ) operations in the worst case. My math doesn't add up.
I would be grateful for help.

Homework Equations

For example:
Find number 8 in the set 1234578.

The Attempt at a Solution

The set contains n = 7 elements.
1) take the middle number 4; 4 < 8
2) take the middle number in the right half of the set 7; 7 < 8
3) in the next right half we have only 1 element and it's 8. done.

Thus I've made 3 operations to find the element 8. 2 to the power 3 equals 8, but
there are only 7 elements in the set. Hence, O(log2(n) - 1) operations.

I don't see why it is log2(n).
Thank you!

 

[Mark44]

Homework Statement

Hello!
Binary search requires O( log2(n) ) operations in the worst case. My math doesn't add up.
I would be grateful for help.

Homework Equations

For example:
Find number 8 in the set 1234578.

The Attempt at a Solution

The set contains n = 7 elements.
1) take the middle number 4; 4 < 8
2) take the middle number in the right half of the set 7; 7 < 8
3) in the next right half we have only 1 element and it's 8. done.

Thus I've made 3 operations to find the element 8. 2 to the power 3 equals 8, but
there are only 7 elements in the set. Hence, O(log2(n) - 1) operations.

I don't see why it is log2(n).
Thank you!

See https://en.wikipedia.org/wiki/Binary_search_algorithm#Performance

 

[Ray Vickson]

Homework Statement

Hello!
Binary search requires O( log2(n) ) operations in the worst case. My math doesn't add up.
I would be grateful for help.

Homework Equations

For example:
Find number 8 in the set 1234578.

The Attempt at a Solution

The set contains n = 7 elements.
1) take the middle number 4; 4 < 8
2) take the middle number in the right half of the set 7; 7 < 8
3) in the next right half we have only 1 element and it's 8. done.

Thus I've made 3 operations to find the element 8. 2 to the power 3 equals 8, but
there are only 7 elements in the set. Hence, O(log2(n) - 1) operations.

I don't see why it is log2(n).
Thank you!

Why would you say the set {1,2,3,4,5,6,7,8} has seven elements? Count them: there are eight of them!

 

[ducmod]

Why would you say the set {1,2,3,4,5,6,7,8} has seven elements? Count them: there are eight of them!

Ray, please, take a look at my example, it has 7 elements :) I don't have 6 in the set :)

 

[haruspex]

Homework Statement

Hello!
Binary search requires O( log2(n) ) operations in the worst case. My math doesn't add up.
I would be grateful for help.

Homework Equations

For example:
Find number 8 in the set 1234578.

The Attempt at a Solution

The set contains n = 7 elements.
1) take the middle number 4; 4 < 8
2) take the middle number in the right half of the set 7; 7 < 8
3) in the next right half we have only 1 element and it's 8. done.

Thus I've made 3 operations to find the element 8. 2 to the power 3 equals 8, but
there are only 7 elements in the set. Hence, O(log2(n) - 1) operations.

I don't see why it is log2(n).
Thank you!

You seem not to understand what the O notation means. If x is a variable that can become very large then O(x) is the same as O(x+1) etc.

 

[Ray Vickson]

Homework Statement

Hello!
Binary search requires O( log2(n) ) operations in the worst case. My math doesn't add up.
I would be grateful for help.

Homework Equations

For example:
Find number 8 in the set 1234578.

The Attempt at a Solution

The set contains n = 7 elements.
1) take the middle number 4; 4 < 8
2) take the middle number in the right half of the set 7; 7 < 8
3) in the next right half we have only 1 element and it's 8. done.

Thus I've made 3 operations to find the element 8. 2 to the power 3 equals 8, but
there are only 7 elements in the set. Hence, O(log2(n) - 1) operations.

I don't see why it is log2(n).
Thank you!

The $\log_2(n)$ count is an asymptotic, worst-case bound. For $n = 7$ we have $\log_2(7) \doteq 2.80735$, and no algorithm can take exactly that many steps.

 

[Ray Vickson]

Ray, please, take a look at my example, it has 7 elements :) I don't have 6 in the set :)

Right: you got me on that. Good one!

 

[ducmod]

The $\log_2(n)$ count is an asymptotic, worst-case bound. For $n = 7$ we have $\log_2(7) \doteq 2.80735$, and no algorithm can take exactly that many steps.

Does it mean that I have to round numbers like 2.80735, and thus get the answer 3? So, the worst case scenario will require 3 steps when n = 7, correct?

 

[Mark44]

You seem not to understand what the O notation means. If x is a variable that can become very large then O(x) is the same as O(x+1) etc.

Does it mean that I have to round numbers like 2.80735, and thus get the answer 3? So, the worst case scenario will require 3 steps when n = 7, correct?

See https://en.wikipedia.org/wiki/Big_O_notation.

 

[Ray Vickson]

Does it mean that I have to round numbers like 2.80735, and thus get the answer 3? So, the worst case scenario will require 3 steps when n = 7, correct?

No: 2.807 is an upper bound on the number of steps, and since the actual number of steps must be an integer, we must have N(steps) ≤ 2.