Can someone please help me with a formula I can use to calculate the complexity of an algorithm?
For example, How large a problem can be solved in 1 second using an algorithm that requires f(n) bit operations, where each bit operation is carried out in 10^-9 second, with the following value for f(n) n!
I have several problems like this so I am not necessarily looking for an answer, but a way to solve.
Thank you, I can see that now and I checked the answer in the back of the book and you are correct. Now I have a really stupid question maybe you can answer it.
Can you tell me why, in the problem it is shown as 10^-9 but when you worked the problem, you used 10^9? What does it mean when you have a negative power? I'm so confused.
Thank you, I can see that now and I checked the answer in the back of the book and you are correct. Now I have a really stupid question maybe you can answer it.
Can you tell me why, in the problem it is shown as 10^-9 but when you worked the problem, you used 10^9? What does it mean when you have a negative power? I'm so confused.
I will try to break this up more
time increases (10^-9) for every value of f(n). So you are really saying (10^-9) + (10^-9) + (10^-9) + ...
which is (10^-9)*f(n)
Now we are restricting this value to 1, because we want to solve for times which are less than or equal to 1. So we get 1 = (10^-9)*f(n)
As topsquark showed, this can be written:
Multiplying both sides by 10^9 we get
now, 10^9 = 1,000,000,000, and f(n) = n! so we can substitute these values in
At this point you can simply take out a calculator to evaluate:
you know:
1! = 1
2! = 2*1
3! = 3*2*1
4! = 4*3*2*1
5! = 5*4*3*2*1
6! = 6*5*4*3*2*1
7! = 7*6*5*4*3*2*1
8! = 8*7*6*5*4*3*2*1
9! = 9*8*7*6*5*4*3*2*1
10! = 10*9*8*7*6*5*4*3*2*1
11! = 11*10*9*8*7*6*5*4*3*2*1
12! = 12*11*10*9*8*7*6*5*4*3*2*1
13! = 13*12*11*10*9*8*7*6*5*4*3*2*1
Most calculators will return a running total, so you could do 1*2 and it will instantly display 2, then you hit *3 and it will instantly display 6, and then you hit *4 and it will instantly display 24, etc.
Some calculators also have factorial buttons, which can simplify matters. You are looking for the first value to exceed 10^9, in this case it is 13, so your solution must be one less than that.
Plugging this into the function for time,
time = (10^-9)n!
we can see that:
if n=12 then time = 0.4790016
if n=13 then time = 6.2270208
So at n=13, it will take over 6 seconds to complete, but at n=12, it will take less than half a second to complete. Since your answers must be integers (factorial function only works on integers) you know it must be the highest integer that is less than 13, and thus you get 12.