0
$\begingroup$

I was wondering what the limitations to an algorithm that runs in O(n!). For example lets take an algorithm that generates all permutations of a list. Now what i am wondering is what the upper bound would roughly be for size of list. I understand that this can vary based on ram/memory. Let's say that this would be ran client side and be expected to work on basically any machine a user would have at his/her home.

Thanks in advance for any insight.

$\endgroup$
  • $\begingroup$ If this is related to your Swiss pairing program, you don't need to generate the list of all permutations. $\endgroup$ – David Richerby Jan 26 '17 at 15:09
  • $\begingroup$ I have no idea what you are asking. In particular, how do the title and the body of your question relate? $\endgroup$ – Raphael Jan 26 '17 at 21:10
  • $\begingroup$ @Raphael they relate because i am wondering how big n would need to be in order to not implement an algorithm that runs in O(n!) $\endgroup$ – Maxqueue Jan 26 '17 at 21:42
2
$\begingroup$

It depends a bit on the constants hidden in the $O$, so no general answer is possible. In my experience you can aim for the low teens. 13! is about six billion. A computer can do about a billion things in a second, so a runtime of a couple of minutes seems reasonable if you only want to enumerate permutations. 15! is already more than a thousand times bigger, so most likely whatever you want to do will take too long.

On my machine counting to 11! in Python takes 14 seconds and counting to 12! takes two and a half minutes. Counting to 13! would hence take about half an hour. Counting to 15! would take about a week.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you this is what i was curious about and i got similar results. Just wanted to hear what other people thought. $\endgroup$ – Maxqueue Jan 26 '17 at 21:44
2
$\begingroup$

Lets do an example.

Lets say you have some operation that takes 1/100th of a second to complete.

Lets say your algorithm needs to use this operation exactly n! times.

Let n = 20

20! operations / 100 seconds per op / 60 seconds per min / 60 min per hour / 24 hours per day / 365 days per year ~= 771468165.962 years.

Personally I don't have that kind of time to wait.

Note: Big O can't be used to calculate execution time like this in general because constants are dropped and operation time isn't the only factor. This is just a rough estimate so give or take a few millennia.

So the size of an acceptable list really depends on how much time you have.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.