Monday, November 15, 2010

An n^n algorithm (or a surefire way to freeze up your memory lickety-split)

     So one of my friends and I were talking about algorithm analysis and tried to think up a quick and dirty n^n algorithm (that is, one which grows on a more than factorial order) and this is what we came up with.  Be forewarned:  Calling this function with an argument of more than 30 is likely to eat all your memory (on the school computer we tried it on we got a BSOD.  Wheeeeee!)

void int sum(int n)
      //base case
      if(n == 0)
          return 1;

      int sum = 0;
      for(int i = 0; i < n; i++)
           sum += sum(i);
      return sum;

This is like the fibonacci series on crack (in terms of the call hierarchy), though it ends up falling into a pattern of simply doubling.  You get a slightly more interesting pattern by switching the initialization of sum from 0 to n, but the main point here is to maximize the number of operations in as little code as possible without generating an infinite loop.