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 of a Problem-Calculation

  1. Mar 2, 2005 #1
    I have been given an assignment, a small one, which simply takes in number of points in cartesian coordinate format: (x, y) - then - the assignment specified that the program needed to calculate distances of every permutation possible - then return with the set(s) of points that had the shortest distance.

    The problem given is simple, and I have coded in C - works perfectly OK.

    But here's the problem:

    What is the number of distance calculations executed by your program for an input instance of "N" points, as a function of "N", expressed in Big-Oh notation? JUSTIFY your answer.

    I know that my program (which I think is efficient enough at this stage) calculates in this many steps:

    [tex]f(x) = \sum_{n=2}^N (x - 1)[/tex]

    I also know that Big-Oh notation is something that f(x) is asymptotic to. For example:

    [tex]g(x) = O(f(x)) = c.f(x) = c.\sum_{n=2}^N (x - 1)[/tex]

    Is this correct way of looking at the Big-Oh notation? How would I find the value of c?

    Thanks

     
    Last edited: Mar 2, 2005
  2. jcsd
  3. Mar 3, 2005 #2
    What's x? Presumably the complexity of your program, for an input of size N is
    f(N) = [some function of N]
    so I don't see where x comes into the picture.

    Ultimately you want to be able to say that
    f(N) = O(g(N))

    meaning that there is some function g(N) such that your function
    f(N) [itex]\leq[/itex] C*g(N)
    whenever N > k for some constants C and k of your choosing (k might be 0). C and k are whatever constants you need to make that inequality true. Depends on what f(N) is, so you need to get your f(N) into a more useful form.

    (As a start, count how many times your program loops as a function of N, and how many operations it performs per loop.)
     
  4. Mar 8, 2005 #3
    I messed up with my x's and N's, the top line should really be f(N). I am having trouble finding g(N) and the constant value C.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Calculating Complexity of a Problem-Calculation
  1. Calculating Pi (Replies: 4)

  2. Favorite Calculators (Replies: 12)

  3. Algebra calculators? (Replies: 9)

  4. Android calculator? (Replies: 3)

  5. Excel + Calculations (Replies: 9)

Loading...