1

I haven't been able to find an example of an algorithm (programming or real world) where the true computation takes n^n computations. I have seen the Traveling Salesman Problem, but that is really n! which is slightly less than n^n. I've also seen the phone book example here. This phone book problem is not really n^n since each original phone book loaded takes a total of n and n copies are made for each original book. Now it's up to n + n^2. The robot then needs to load each additional copy which is also n^2. Add all these up and you get n + 2n^2. Which, since we look at the largest exponent, is only x^2.

Can someone please give me an example of something that truly takes n^n?

Community
  • 1
  • 1
OverflowingJava
  • 101
  • 10
  • that phone book example has complexity n*n not n^n...probably you read it wrong. As I did just(yes! I read your question wrong). – Rohit Rawat Jan 06 '16 at 06:14
  • 1
    http://stackoverflow.com/questions/6156224/are-there-any-real-onn-algorithms -> maybe you can get some help from this link. – Rohit Rawat Jan 06 '16 at 06:46
  • Computing the product of all permutations of `n` values with a primitive algorithm is exponential. BTW: The TSP is not `O(n!)`, it's rather that its brute-force algorithm is. There are other algorithms for TSP that have other complexities. – Ulrich Eckhardt Jan 06 '16 at 07:19
  • Are you specifically looking for n^n, or will anything in Omega(2^(n log n)) do? – G. Bach Jan 06 '16 at 10:15
  • @G. Bach - I'm specifically looking for n^n complexity. – OverflowingJava Jan 06 '16 at 17:10

1 Answers1

3

An example of recursive O(nn) function that counts to nn 

long long pownn(int n, int depth) {
    if ( ! depth) return 1;
    long long ll = 0;
    int i = n;
    while (i--) ll += pownn(n, depth-1);
    return ll;
}

called long long result = pownn(n, n);

this kind of algorithm is like what can be found in some games where theoretically each searchable position gives itself n other searchable positions, having the search depth set to n. Practically, games (like chess) can be optimized (minimax / alpha-beta / memoization-like: millions of positions stored / position analysis...), and the search may go farther than depth n after eliminating "useless" intermediate positions. Thus "only" a few millions positions are analyzed.

Déjà vu
  • 28,223
  • 6
  • 72
  • 100
  • 1
    Can you explain why an unoptimized search for all possible chess moves is n^n? – OverflowingJava Jan 06 '16 at 17:15
  • 3
    It's a theoretical situation, as chess will have more or less than a constant number of positions after a move is done. Anyway, say a given positions has 10 potential moves, and each of these moves gives the opponent 10 potential moves etc... The 1st level gives 10 branches, each of them gives 10 branches etc... At depth 10, the number of positions to be analyzed is 10 x 10 x ... x 10 (10 times), ie 10^10. Replace 10 with *n*... – Déjà vu Jan 07 '16 at 08:35
  • 1
    That actually makes sense to me. Thanks. – OverflowingJava Jan 11 '16 at 01:50