Re: Why is indexOfObjectIdenticalTo: *far* faster than indexOfObject: ?
Re: Why is indexOfObjectIdenticalTo: *far* faster than indexOfObject: ?
- Subject: Re: Why is indexOfObjectIdenticalTo: *far* faster than indexOfObject: ?
- From: Robbie Haertel <email@hidden>
- Date: Thu, 23 Dec 2004 10:30:21 -0700
In my computer science classes we were always taught to worry about
the worst case, and we were told that that is usually what O
represents. However, we were also taught how to calculate best case
and average case (probably the most useful measurement). Anyway, for
the sequential travesal of the array, the average case and worst case
are both O(n).
On Thu, 23 Dec 2004 18:13:31 +0100, Aurélien Hugelé
<email@hidden> wrote:
>
> On 23 déc. 04, at 16:27, Heinrich Giesen wrote:
>
> >
> > On 23.12.2004, at 15:02, Aurélien Hugelé wrote:
> >
> >> IMO indexOfObject is just Olog(n)
> > no, it is O(n)
>
> yes it is my mistake ;)
>
> >> because it needs full traversal of
> >> the array
> > and because of the sequential search it is O(n).
> > A binary search is O( log(N) ), hashing is something like O(1).
>
> you are right again
>
> >
> >> if the searched object is the last one.
> > No.
> > The O-Notation is usually not interested in worst case scenarios.
> >
>
> i did not know that :) i thought we should always think about the worst
> case scenario !
>
> > Heinrich Giesen
> > email: email@hidden
> >
> >
>
>
> _______________________________________________
> Do not post admin requests to the list. They will be ignored.
> Cocoa-dev mailing list (email@hidden)
> Help/Unsubscribe/Update your Subscription:
>
> This email sent to email@hidden
>
>
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Cocoa-dev mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden