CODEWITHSUNDEEP
algorithmtime-complexity
OverflowingJava
OverflowingJava

Reputation: 101

Exponential Time Complexity Example (n^n)

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?

Upvotes: 1

Views: 2836

Answers (1)

Déjà vu
Déjà vu

Reputation: 28830

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.

Upvotes: 3

Related Questions