
Re: binary search with arbitrary or random split
Posted:
Jul 24, 2012 1:10 PM


pam <pamelafluente@libero.it> writes:
> On Jul 24, 4:27 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote: > >> >> would be logarithmic. The key distinction is between reducing the >> range by a factor of n or by a fixed amount independent of n. >> >>  >> Ben. > > > Very interesting Ben (i like the point you made on the dependence on > n). > After all if there were no dependence on n, we would not be really > "dividing" anything ;) > > So, as far as the splitting point is some fraction of n, say n/k, > where > 1 < n/k < n we are within O(logn). Power of "divide and conquer". ;) > > > The only point which remains now a little unclear to me > is just the case (random splitting) where we allow n/k = 1, n. > > > Now i see your argument. In practice you say, since of each > array of size n, i "could" get to pick up always 1 (or n), > then i have to say that the search could take O(n).
I'd say "in theory" rather than "in practice". In practical terms, the worst case of a randomly chosen split is of little importance. It's significance is theoretical.
> (Clearly, we could easily fix that by saying "dont pick 1 or n" > in the random splitting.)
What would that fix? uniform(2, n1) is as bad as uniform(1, n).
> That is fine. However, we must also observe that in the asymptotic > analysis as n tends to infinity there is a region, in this case, say > intuitively > between 2 bounds O(logn) and O(n), whose probability can be made > arbitrarily small.
I don't understand this, but it seems to lead to something I agree with so there's probably little point in explaining it further.
> So, in essence, any experiment done with any kind of data * provided n > is large > enough * will eventually lead to observe a complexity of O(logn), and > not O(n)
Yes, experiments will usually find the averagecase performance.
However: You can't observe worstcase complexity as this example shows. You simply won't see that uniform splitting is, theoretically, worse the logarithmic because experiments will give you the average.
By the way, your use of big O is getting out of hand (we all do it because it's become a shorthand for something else). You can't say that something has a complexity of O(log(n)) and not O(n). Proper binary search is O(n), it just happens to O(log(n)) as well! If this surprises you, check the definition.
> So it becomes probably a matter of how complexity is defined within in > a probabilistic context.
Hmmm. To what does "it" refer? If you mean "the answer" then of course, but that's just a tautology. What the square root of 9 is depends on how we define the square root in the context of comp.theory.
"Complexity", unadorned, usually means worstcase complexity.
> I think that including events with 0 probability might be rather > misleading.
It would be wrong, not misleading. That you say this, suggests that did not agree with my rather detailed previous message. Which bit suggests that something with zero probability is being considered?
> Take for instance the case where one switches for instance from > 1 < n/k < n to the condition 1 <= n/k < n.
I don't understand this.
> Imagine you are applying the procedure to factorize a large modulus or > something. Now would you really > support that in practice you go from O(log n) to O(n) ?
I think you are saying that some change (characterised by the two inequalities above) to some as yet unspecified algorithm for factorising numbers would not alter it's complexity bound from log(n) to n "in practice".
If that's right, I can't say. I don't understand the two inequalities and I have no idea what factoring algorithm you have in mind. Also, I don't know what "in practice" means. I know what complexity means "in theory". In practice, I measure runtimes, but that's not complexity analysis. Another meaning of "in practice" could be that you want to do "expected averagecase cost" rather than "worstcase cost" analysis since that's a measure that's often more useful for practical purposes.
> It would be rather far from being meaningful, as to how one normally > understands complexity. No ?
Well it might be, but I just don't understand the setup.
 Ben.

