Results 1 to 10 of 10

Math Help - Complexity of Algorithm

  1. #1
    Member
    Joined
    May 2008
    Posts
    109

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by sjenkins View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2008
    Posts
    109
    Yes, that seems to be what the question is saying.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2008
    Posts
    109
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    May 2008
    Posts
    109
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,068
    Thanks
    372
    Awards
    1
    Quote Originally Posted by sjenkins View Post
    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.
    10^{-9} \equiv \frac{1}{10^9}

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

    -Dan
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    May 2008
    Posts
    109
    Oh, that's simple. Thanks for your help!!!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by angel.white View Post
    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:
    1 = \frac {f(n)}{10^9}

    Multiplying both sides by 10^9 we get

    10^9 = f(n)

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

    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    May 2008
    Posts
    109
    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] complexity theorie, deterministic turing-machines, time complexity
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 19th 2011, 06:44 AM
  2. O(sin n), Ω(sin n), Θ(sin n) complexity
    Posted in the Advanced Math Topics Forum
    Replies: 4
    Last Post: August 18th 2010, 06:55 AM
  3. complexity of this algorithm in my program
    Posted in the Math Software Forum
    Replies: 1
    Last Post: September 3rd 2009, 01:36 PM
  4. Matlab - Determining the complexity of an algorithm
    Posted in the Math Software Forum
    Replies: 5
    Last Post: March 19th 2009, 03:25 AM
  5. Complexity of Prime Algorithm
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 3rd 2006, 01:09 PM

Search Tags


/mathhelpforum @mathhelpforum