# Complexity of Algorithm

• Jun 21st 2008, 08:04 AM
sjenkins
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.
• Jun 21st 2008, 08:53 AM
angel.white
Quote:

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?
• Jun 21st 2008, 09:08 AM
sjenkins
Yes, that seems to be what the question is saying.
• Jun 21st 2008, 09:22 AM
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
• Jun 21st 2008, 09:32 AM
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.
• Jun 21st 2008, 09:33 AM
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.
• Jun 21st 2008, 09:38 AM
topsquark
Quote:

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.

$\displaystyle 10^{-9} \equiv \frac{1}{10^9}$

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

-Dan
• Jun 21st 2008, 09:50 AM
sjenkins
Oh, that's simple. Thanks for your help!!!
• Jun 21st 2008, 10:01 AM
angel.white
Quote:

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:
$\displaystyle 1 = \frac {f(n)}{10^9}$

Multiplying both sides by 10^9 we get

$\displaystyle 10^9 = f(n)$

now, 10^9 = 1,000,000,000, and f(n) = n! so we can substitute these values in

$\displaystyle 1,000,000,000 = n!$

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.
• Jun 21st 2008, 10:13 AM
sjenkins
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!