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?


    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook