Question

@ http://www.mathsisfun.com/sets/np-complete.html
"factorial time": t = n!


Lets say the program could solve a 20-city problem in 1 second, then a 21-city problem would take about 21 seconds to solve. And a 22-city problem would take about 462 seconds (over 7 minutes), and a 30-city problem would take 3 Million Years. Ouch!
Now, the problem I am facing that in solution, he has use 21 * 22 = 462 whereas t = n! where has he used the factorial?

Answer 1

Secondly, when he uses "exponential time": t = 2^n

So a program that solved 20 cities in 1 second would take about 10 minutes to solve a 30-city problem and a 60-city problem would take 35,000 Years.

he has solved 10 minutes by multiplying 20*30 where has he used t=2^n formula?

Answer 2

It's rather that \(t\) is proportional to \(n!\). The actual formula for \(t\) is\[t = \dfrac{n!}{20!}\]

Answer 3

With the second one, it's a similar case. What you have to consider is the proportionality. The formula is:\[\Large t = \frac{2^n}{2^9}=2^{n-9}\]

Answer 4

@yakeyglee thanks
I understand the first formula but I don't understand the second formula where has this 2^9 come from?

Answer 5

@yakeyglee plzzz help me to understand it

Answer 6

My bad it actually should be \[\Large t = \frac{2^n}{2^{\color{red} {20}}}=2^{n-\color{red}{20}}\]This is just to force the appropriate values... for instance \(n=20\) makes \(t=2^0=1\). It's still proportional because I'm just scaling by a constant.

Answer 7

got it thanks a tonne