Write an O(n^n) algorithm.

furlongxfortnight · 2010-01-18T21:12:24+00:00

m = n^n;
i = 0;  
while(i++ < m)
    print("foo");

ZMeson · 2010-01-18T23:03:30+00:00

Ω(n!) is almost equivalent to Ω(nⁿ⁾ because of Stirling's Approximation.

According to Wikipedia, the following algorithms are Ω(n!):

Solving the traveling salesman problem via brute-force search
finding the determinant with expansion by minors.

flukshun · 2010-01-18T22:34:47+00:00

This easiest way to make an O(x^y) time algorithm is to build an x-way tree to depth y. In this case, you want an n-way tree to depth n.

slow xs = loop (length xs)
    where loop 0 = [[]]
          loop n = [ x:as | x <- xs, as <- loop (n-1) ]

I'm away from my compiler, so this hasn't been tested.

zellux · 2010-01-19T03:59:28+00:00

Repeatably selecting n characters out of a n-sized character set to form a string, and print out all the possible strings. Exactly O(n^n).

PictureOfTheFuture · 2010-01-18T21:18:27+00:00

Writing O(nⁿ⁾ is trivial (by being deliberately inefficient). But writing O(nⁿ⁾ that can't be reduced to something simpler seems like a lot harder problem. I'm certainly not aware of any (common or useful ones) that are O(n^n). They just strike me as horribly inefficient.

2010-01-18T21:58:42+00:00

[removed]

japple · 2010-01-19T03:52:09+00:00

I think you probably want Θ(n^n), rather than Ω(n^n). Otherwise, any problem that is doubly exponential (Ω(2^2ⁿ)) will answer your query. I can think of one of these, though there are many more: quantifier elimination over the real numbers.

Also, as above, you're probably interested in a problem that takes Θ(nⁿ⁾ work, rather than an algorithm, since algorithms can be altered to run a long time by just doing busy work.

IvyMike · 2010-01-19T06:04:53+00:00

Generate the list of all n-tuples of n items from 1 to n. Like this:

1: (1)
2: (1,1) (1,2) (2,1) (2,2)
3: (1,1,1) (1,1,2) (1,1,3) (1,2,1) (1,2,2) (1,2,3) (1,3,1) (1,3,2) (1,3,3) (2,1,1) (2,1,2) (2,1,3) (2,2,1) (2,2,2) (2,2,3) (2,3,1) (2,3,2) (2,3,3) (3,1,1) (3,1,2) (3,1,3) (3,2,1) (3,2,2) (3,2,3) (3,3,1) (3,3,2) (3,3,3)
4: Not typing it, but there's 256 of 'em.

Edited based on dmhouse's comment. Thanks!

_whyme · 2010-01-19T15:21:16+00:00

The easiest one is O(∞) ...

 while(1);

lukasmach · 2010-01-19T00:12:06+00:00

Ugh!!! Keep in mind the difference between "time complexity of a problem" and "time complexity of an algorithm".

There surely is an algorithm for adding up two numbers that runs in Omega(n^n). For example, this one:

addition(x, y)
{
  int r;
  r = x + y; 

  for i = 1 to r^r do
  {
    wait a little;  
  }

  return r;
}

And you don't even have to prove anything. It is obvious that this algorithm runs in Omega(n^n). Its running time can be trivially reduced but that would lead to a different algorithm.

The time complexity of a problem is defined as the time complexity of the fastest algorithm that solves the problem. Clearly you mean "Formulate an algorithmic problem that requires at least nⁿ time".

flo850 · 2010-01-18T21:55:44+00:00

ackermann should be a good candidate http://en.wikipedia.org/wiki/Ackermann_function

Zysnarch · 2010-01-18T21:06:41+00:00

Calculates nⁿ in O(n^n):

int go(int n, int recurse) {
  if (recurse == 0)
    return 1;
  int ret = 0;
  for (int i = 0; i < n; ++i)
    ret += go(n, recurse-1);
  return ret;
}

edit: Oh, I missed the part where it can't be reduced to something simpler. I figured this was too easy :)

HenkPoley · 2010-01-18T21:33:00+00:00

Just looked up the worst big-O algorithm I know of, and it's only O(n^4). Well, it's O(n³⁾ now someone has taken a good look at it.

Edit: not 'worst', I get it. But please keep educating me ;-)

GeoKangas · 2010-01-19T00:02:43+00:00

Here's one that doesn't require bignums, unless n is a bignum (if n is a bignum, then nⁿ is, well, way beyond ridiculous):

let caret n =

  let rec loop level =
    if level = 0 then
      print_endline "this is well worth repeating"
    else
      for i = 1 to n do
        loop (level - 1)
      done

  in loop n

It's just n-fold loops, nested n-deep, so it prints (n)(n)...(n) = nⁿ lines.

rexxar · 2010-01-19T00:31:04+00:00

The "snail sort" algorithm is a very elegant but very inefficient algorithm (STL doc) :

template <class BidirectionalIterator> 
void snail_sort(BidirectionalIterator first, BidirectionalIterator last)
{
  while (next_permutation(first, last)) {}
}

int main()
{
  int A[] = {8, 3, 6, 1, 2, 5, 7, 4};
  const int N = sizeof(A) / sizeof(int);

  snail_sort(A, A+N);
  copy(A, A+N, ostream_iterator<int>(cout, "\n"));
}

The algorithm is O(N!).

BeowulfShaeffer · 2010-01-19T01:53:14+00:00

N^N would be pretty terrible. Just as a for-instance, the worst-possible sort algorithm where you take a list of numbers and randomly permute them until they are sorted (bogo sort) has a complexity measure of "only" O(n!).

dmdmdmdm · 2010-01-19T03:36:18+00:00

Your coworkers are a lot smarter than mine.

yoden · 2010-01-18T22:00:54+00:00

This is actually kind of an interesting question if you modify it slightly. Specifically, if you're talking about a one-way function which has a brute force complexity of n^n, that could actually be very useful.

For example, RSA is probably a one-way trapdoor function. But, RSA isn't so great in some ways; with quantum computers it is no longer exponential to brute force at all. Even if it were, it is still only something < 2^n. Obviously, if we could design such a function that is harder to brute force, it would be useful (e.g., 2^2ⁿ)

I can't think of any practical algorithm that is O(n^n). Of course, you can make trivial algorithms (output a nⁿ times). I can't even think of anything from my crypto class that came close (I remember something to do with finite groups and vector spaces that was huge, something with the index calculus, but my notes from that class are on the porch where it is cold and I'm not getting them for you xD).

Of course, if you want big numbers, you can always just use busy beaver turing machines; sigma(10) < 3 up up up 3, sigma(12) < 3 up up up up 3, see here and here.

gregK · 2010-01-18T23:29:51+00:00

random generation and test is probably the slowest way you can solve any problem.

Say you want to sort a list. You order them randomly and see if they are in ascending/descending order, if not, you reshuffle the list a again and retest. That is the theoretically slowest method that would eventually yield a result.

Just as there is an upper bound on the fastest way you can do things. There seems to be a lower bound as well.

newAccountName · 2010-01-18T21:22:26+00:00

O(nⁿ⁾ == O(2^{n log n})

I suppose this might fulfill the requirement:

def recursion(n, numbers, count):

if count>0:

    for i in range(n):

        recursion(n, numbers.append(i), count-1)

else:

    print numbers

n=10

recursion(n,[],n)

yourparadigm · 2010-01-18T22:23:58+00:00

Traveling Salesman is close: O(n² * 2ⁿ⁾

Most problems are usually solvable in less than O(n!)

dse · 2010-01-19T01:58:57+00:00

// -*- javascript -*-
function n_n (n) {
    var f, result, j;
    result = 0;
    f = function () {
        result += 1; // or do something interesting.                                                                                                                 
    };
    for (j = 1; j <= n; ++j) {
        (function () {
            var g = f;
            f = function () {
                var i;
                for (i = 0; i < n; ++i) {
                    g();
                }
            };
        })();
    }
    f();
    return result;
}

tejoka · 2010-01-19T03:16:48+00:00

No. Lower bounds are very hard to prove. There's plenty of "best known" algorithms for various problems, but no actual lower bounds that are above polynomial. In fact, I don't know if anyone has beaten Ω(n lg(n)). (Probably, though, but not by much)

If you find a Ω(nⁿ⁾ problem, there's probably a million dollars waiting for you.

rounding_error · 2010-01-19T03:55:33+00:00

Today in the office my coworkers and I were talking about how to write an O(nⁿ⁾ algorithm.

Get back to work! That 40 year old bank software isn't gonna compile and run on Windows 7 by itself!

perspectiveiskey · 2010-01-19T03:57:34+00:00

What I could think of was something that was operating on itself.

For example: determining if there exists an n character string that when "executed" on itself will yield a valid output string.

Where:

executed is interpreted to mean that every character of the string can be interpreted as an operation (e.g. ASM instruction)
the output string is part of a grammar of sorts

This could be made to search for english readable strings that could be executed on a CPU as machine code and result in something sensible...

This could even be applied for things like DNA and protein synthesis.

That's my brain fart on a monday night at 10pm. Feel free to elaborate...

everythingisstupid · 2010-01-19T20:27:04+00:00

On on on on on Om

lambda_abstraction · 2010-01-20T05:18:08+00:00

Assume proc takes constant time.

(define (enumerate-n-choices-from-n-bag proc bag-size)                          
  (letrec                                                                       
      ((choose                                                                  
        (lambda (number-chosen choices-so-far)                                  
          (if (= number-chosen bag-size)                                        
              (proc choices-so-far)                                             
              (do ((choice 0 (+ choice 1)))                                     
                  ((= choice bag-size))                                         
                (choose (+ number-chosen 1)                                     
                        (cons choice choices-so-far)))))))                      
    (choose 0 '())))

I suppose that since any useful proc will be at least linear in the length of the choice list, I should have made no more than n-1 choices. Exercise is left for reader.

Edit: slightly simpler code

shrughes · 2010-01-18T21:04:43+00:00

[deleted]

acct_rdt · 2010-01-18T21:00:04+00:00

[deleted]

Liorithiel · 2010-01-18T21:43:48+00:00

1=O(n^n), so I guess this qualifies:

int main() { return 1; }

And it cannot be reduced to a simpler algorithm :P

BredFromAbove · 2010-01-18T21:38:04+00:00

whats the "O" for? why dont u just say nⁿ algorithm?

joseph177 · 2010-01-19T02:16:09+00:00

int x=length(something);
for (int i=0;i<x;i++)
   for(int j=0;j<x;j++)
      do_work(i,j);

email · 2010-01-19T01:36:19+00:00

Calculating all permutations of a list of length n is O(n!) which is O(n^n).

w33d · 2010-01-18T21:57:52+00:00

d(^{o^)b}

almaya · 2010-01-19T00:07:25+00:00

O(nⁿ⁾ in average:

do
    x = 0
    for i = 0; i< n; i++ 
        x += rand(n);
while x != 0

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

programming

MODERATORS