I'm a non-CS grad student working on an algorithm which would be an alternative to conventional GPS position estimation algorithms. My advisor insists that I must compare the run-time of these algorithms. I understand that simply timing the two algorithms is not a good measure for comparison for several reasons but I'm having trouble finding a good way to compare them.

I am familiar with big-O notation, but my understanding is that it is a good measure for understanding how an algorithm scales as the size of the input approaches infinity. For GPS problems, the size of the input depends on the number of available satellites which is obviously finite (probably never larger than 25 or so).

For such a scenario what would be the best way to compare efficiency?

  • 2
    $\begingroup$ The only way is exactly what you ruled out – run experiments and determine the answer empirically. If your advisor is against that, then perhaps you should make up numbers; this will be as good, or better, than any other method. $\endgroup$ – Yuval Filmus Oct 6 '16 at 2:42
  • $\begingroup$ Thanks. I've run a few experiments. I just feel like it would look silly in a paper... Maybe I'll just run a ton of experiments with any data I can get a hold of... $\endgroup$ – somerandomdude Oct 6 '16 at 5:15
  • 1
    $\begingroup$ Can you derive a function out of the algorithms? $\endgroup$ – blade Oct 8 '16 at 2:56
  • $\begingroup$ @blade what do you mean by that? I can't make it into a single function. I can make it into multiple linear algebra relationships though. $\endgroup$ – somerandomdude Oct 10 '16 at 3:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.