On Sat, Dec 20, 2008 at 11:50 PM, Antony Blakey <[email protected]> wrote: > > On 21/12/2008, at 3:15 PM, Paul Davis wrote: > >> On Sat, Dec 20, 2008 at 11:32 PM, Antony Blakey <[email protected]> >> wrote: >>> >>> On 21/12/2008, at 2:54 PM, Paul Davis wrote: >>> >>>> View update times should be linear in terms of *new* records. >>> >>> Well, with a factor to deal with the reduction, which isn't O(n). >>> >> >> Kinda. I'm pretty sure they're still O(N), just not as pre calculated >> as one might expect. > > I would have thought + a tiny O(log M) where M is determined by the grouping > size of the partial reductions. >
Hmm. I don't think so. Technically we could change the implementation to feed reduce functions a single map-row at a time which would be O(N). Might end up violating some (incorrect) expectations of reduce input, but I'm pretty certain it shows that it's O(N). > Antony Blakey > -------------------------- > CTO, Linkuistics Pty Ltd > Ph: 0438 840 787 > > Don't anthropomorphize computers. They hate that. > > >
