Income statements - multiple businesses

[Derek Atkins]

Quoting Jeff Carneal <jeff-ml at carneal.com>:

>> E.g. some of them may be O(n^2) or even
>> worse, so as your datafile gets larger the reports take even longer!
>
> Just out of curiousity, do you know story with that?  I'm having  
> trouble envisioning anything worse than O(n) for simple reports like  
> these...

It's easy to code up a bad algorithm.  Here's a bad one:

  for i in splits {
    found = false;
    for j in found items {
      if ($i in $j) { add $i to $j; found = true; break; }
    }
    if (!found)
       create new item from $i;
  }

This is worse than O(n)..   And it's quite possible to be much worse
than this.

-derek

-- 
       Derek Atkins, SB '93 MIT EE, SM '95 MIT Media Laboratory
       Member, MIT Student Information Processing Board  (SIPB)
       URL: http://web.mit.edu/warlord/    PP-ASEL-IA     N1NWH
       warlord at MIT.EDU                        PGP key available