1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Calculating complexity

  1. Sep 19, 2004 #1
    Hello, I am trying to understand how to solve problems relating to time complexity of algorithms, esp. problems of the following kind:

    An algorithm takes 0.5 ms for input size 100. How long will it take
    for input size 500 if the running time is the following:
    linear, nlogn, n^2, N^3

    An algorithm takes 0.5 ms for input size 100. How large a problem
    can be solved in 1 min if the running time is the following:
    linear, nlogn, n^2, n^3

    I think I have a general idea of what is asked but cannot figure out how to find it mathematically. Could someone be kind enough to explain it step by step?
    Appreciate your help.
     
  2. jcsd
  3. Sep 19, 2004 #2

    Tide

    User Avatar
    Science Advisor
    Homework Helper

    If t varies as f(n) then
    [tex]\frac {t}{t_0} = \frac {f(n)}{f(n_0)}}[/tex]
     
  4. Sep 19, 2004 #3
    Thanks a lot, I think I got the first problem type, but I still have trouble with the second. Here is how I reasoned for O(n^3):
    0.5/60*10^3 = 100^3/n^3, and then I solve for n^3 and take cube root but do not come up with the right answer. What am I doing wrong?
    Thanks in advance.
     
  5. Sep 19, 2004 #4

    Tide

    User Avatar
    Science Advisor
    Homework Helper

    It looks like you didn't cube the 60 on the left hand side.
     
  6. Sep 19, 2004 #5
    Why do I need to cube 60?
    1 min = 60*10^3(ms), it's time.
    t0/t = n0^3/n^3 hence
    0.5/60*10^3 = 100^3/n^3. Is that wrong? Could you then explain how this works?
    Thanks again.
     
  7. Sep 19, 2004 #6

    Tide

    User Avatar
    Science Advisor
    Homework Helper

    Oops! Sorry - I wasn't thinking - that was wrong.

    What you did looks okay.
     
  8. Sep 19, 2004 #7
    How do I solve the case where O(nlog(base 2)n)? I know I can represent it in a different way: 2^(number/n) = n, or I can change bases where n*ln(n) = number*ln2, but how do I solve this?
    Thanks for help.
     
    Last edited: Sep 19, 2004
  9. Sep 20, 2004 #8

    Tide

    User Avatar
    Science Advisor
    Homework Helper

    The log problem is different from the others because you can't write a simple solution for it. You will have to resort to obtaining a numerical estimate. For example, you could use successive approximations which means you find a value of N which is too small and one that is too large then pick a point in between and see if that's too large or small. Adjust your range appropriately and repeat until you have the desired accuracy.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Calculating complexity
  1. Complex lens (Replies: 1)

  2. Complex number (Replies: 13)

Loading...