Calculating Complexity of a Problem-Calculation

[kioria]

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

 

[gnome]

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.)

 

[kioria]

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.