|
|
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, n-1) 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 average-case performance.
However: You can't observe worst-case 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 short-hand 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 worst-case 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 run-times, but that's not complexity
analysis. Another meaning of "in practice" could be that you want to do
"expected average-case cost" rather than "worst-case 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 set-up.
--
Ben.
|
|
