title: Are there any real O(n^n) algorithms?
body: <p>Is there any real Algorithm with a time complexity O(n^n), that isn't just a gimmick?</p>
  
  <p>I can create such an Algorithm, like computing n^n in O(n^n) / Θ(n^n):</p>
  
  <pre><code>long n_to_the_power_of_m(int n, int m) {
      if(m == 0) return 1;
      long sum = 0;
      for(int i = 0; i &lt; n; ++i)
          sum += n_to_the_power_of_m(n, m-1);
      return sum;
  }
  </code></pre>
  
  <p>(needs more than 4 minutes to compute 10^10)</p>
  
  <p>Or other way around: Are there any Problems, which cannot be solved better than in O(n^n)?</p>