Hello and welcome to our community! Is this your first visit?
Enjoy an ad free experience by logging in. Not a member yet? Register.

1. ## Binary Search

How many times would the binary search (O(logn)) loop, assuming you did not find the data, if:
n = 10? 3
n = 100? 6
n = 1000? 12
n = 10,000? 18
n = 100,000? 24
n= number of elements in array. My answers are above. Are they correct?

• I got:
1
2
3
4
5

But it has been a while since I've done big O notation so I might have goofed it up.

• ## Users who have thanked oracleguy for this post:

twodayslate (09-09-2008)

• @oracleguy: log in cs typically denotes the natural log (aka ln)

10 : 3
100 : 5
1000 : 7
10000 : 10
100000 : 12

EDIT: should be "denotes the log base 2" Thus my answers are wrong for log base 2.

• ## Users who have thanked Trinithis for this post:

twodayslate (09-09-2008)

• ...but the actual worst-case performance of the binary search is the binary logarithm of n, O(log2 n). Trick question?

ceil(log2 n == log n/log 2) =
10 => 4
100 => 7
1000 => 10
10000 => 14
100000 => 17

(the answer is supposed to round up, right? the actual number depends on which bound the missing search value is closest to and how the implementation rounds when picking midpoints.)

• ## Users who have thanked ralph l mayo for this post:

twodayslate (09-09-2008)

• lol everyone has a diffferent answer..id help if i knew how

• Originally Posted by Trinithis
Oh ok; that is kind of dumb. If it is supposed to be the natural log why not just write ln and be mathematically correct?

• ## Users who have thanked oracleguy for this post:

twodayslate (09-09-2008)

• Because just writing log you don't tell anybody which logarithm you're talking about - the default assumption is for that reason the most useful one, in other words the natural logarithm.

Which logarithm do you consider a better default? Decimal? Binary? The binary logarithm is at least somewhat useful for many algorithms, the decimal logarithm less so.

• ## Users who have thanked liorean for this post:

twodayslate (09-09-2008)

• I have not learned decimal so IDK about that...

So what is the right answer? ralph looks the closest...

Here are the steps for 10?
10
5
3
1

So 3 is correct?

• Wow, I'm dumb too. I meant log base 2, not ln . . . and I did my calculations using ln instead of log2. ralph's answers are the ones I would use.

Another reason why people just say log instead of log base x is due to the fact that big O (and family) factors out the constant factors and all logs are just some constant factor of one another.

• Originally Posted by twodayslate
I have not learned decimal so IDK about that...

So what is the right answer? ralph looks the closest...

Here are the steps for 10?
10
5
3
1

So 3 is correct?
No, the steps for 10 with that rounding scheme (ceil or closest, assuming the search is for 0) are:
5
3
2
1

Or if it rounds to the floor:
5
2
1

100, ceil or closest:
50
25
13
7
4
2
1

100, floor:
50
25
12
6
3
1

I'm pretty sure my numbers are correct for actual implementations of the binary search, but they don't reflect O(log n), rather O(log2 n).

• log base two n is correct.

So technically there are two answers then?

• Ralph you are correct! Major props!

10 => 4
100 => 7
1000 => 10
10000 => 14
100000 => 17

•