twodayslate

09-08-2008, 01:42 AM

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?

oracleguy

09-08-2008, 05:06 AM

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.

Trinithis

09-08-2008, 07:40 AM

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

Here are the answers.

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.

ralph l mayo

09-08-2008, 09:16 AM

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

tman11580

09-08-2008, 12:15 PM

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

oracleguy

09-08-2008, 04:06 PM

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

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?

liorean

09-08-2008, 10:40 PM

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.

twodayslate

09-08-2008, 11:12 PM

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?

Trinithis

09-08-2008, 11:37 PM

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.

ralph l mayo

09-08-2008, 11:38 PM

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

twodayslate

09-08-2008, 11:56 PM

log base two n is correct.

So technically there are two answers then?

twodayslate

09-10-2008, 02:12 AM

Ralph you are correct! Major props!

10 => 4

100 => 7

1000 => 10

10000 => 14

100000 => 17