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.

## Monday, November 15, 2010

Subscribe to:
Posts (Atom)