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?

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?
Last edited by twodayslate; 09082008 at 01:46 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.
OracleGuy
twodayslate (09082008)
@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.
Last edited by Trinithis; 09082008 at 11:40 PM.
Trinithis
twodayslate (09082008)
...but the actual worstcase 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.)
Last edited by ralph l mayo; 09082008 at 09:23 AM.
twodayslate (09082008)
lol everyone has a diffferent answer..id help if i knew how
twodayslate (09082008)
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.
liorean <[lio@wg]>
Articles: RegEx evolt wsabstract , Named Arguments
Useful Threads: JavaScript Docs & Refs, FAQ  HTML & CSS Docs, FAQ  XML Doc & Refs
Moz: JavaScript DOM Interfaces MSDN: JScript DHTML KDE: KJS KHTML Opera: Standards
twodayslate (09082008)
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?
Last edited by twodayslate; 09082008 at 11:22 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.
Trinithis
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