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.(adsbygoogle = window.adsbygoogle || []).push({});

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

But here's theproblem:

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

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Calculating Complexity of a Problem-Calculation

**Physics Forums | Science Articles, Homework Help, Discussion**