Thread: Complexity of Algorithm

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.

Originally Posted by sjenkins

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.

Are you saying f(n) = n!, and time = (10^-9)*f(n), and being asked to solve for time = 1?

Yes, that seems to be what the question is saying.

I don't know a purely mathematical approach, but you could say

time = 1 = (10^-9)f(n)

so 10^9 = f(n) = n!

then plug in a few values for n

Since 12! = 479001600
which is less than 10^9

and 13! = 6227020800
which is more than 10^9

I would say n = 12

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.

Originally Posted by sjenkins

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.

The negative exponent means that the expression is in the denominator.

-Dan

Oh, that's simple. Thanks for your help!!!

Originally Posted by angel.white

I don't know a purely mathematical approach, but you could say

time = 1 = (10^-9)f(n)

so 10^9 = f(n) = n!

then plug in a few values for n

Since 12! = 479001600
which is less than 10^9

and 13! = 6227020800
which is more than 10^9

I would say n = 12

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.

Thank you so much for going into detail for me. It really helps when I can see step by step what I need to do!