CODEWITHSUNDEEP
performancealgorithmcompare
Kelly Gan
Kelly Gan

Reputation: 65

compare the running times of two algorithms

I just want to confirm whether my interpretation and calculation are correct or not. Please do correct me if I am wrong.

The running times for A's algorithm and B's algorithm are 8.26789 seconds and 814.21416 seconds, respectively.

Is it correct if I said that A is 98.98% faster than B by using the calculation: (1-8.26789/814.21416)*100% ?

Thank you.

Upvotes: 1

Views: 1717

Answers (2)

Peter Webb
Peter Webb

Reputation: 681

While amdb's answer is correct, if this is a homework exercise I suspect it may be a trick question designed to test your knowledge of computational complexity.

You cannot tell anything whatsoever about the relative speeds of Algorithms A and B based on a single measurement.

To pick an example, the quicksort algorithm is O(n log n) and is a faster algorithm than the bubblesort which is O(n^2)) if you are sorting lots of numbers. But if you benchmarked each sorting just 3 numbers, the bubble sort would almost certainly run faster than the quicksort. The performance against one set of inputs tells you nothing about the comparative performance of the algorithms, it just tells you the relative performance of the algorithm with that particular input, which is not how computational complexity is measured.

Upvotes: 1

amdn
amdn

Reputation: 11582

Since you want to be able to say how much faster A is than B it is best to define this in terms of speed. When A is 2X faster than B it is understood that the speed of A is twice the speed of B. Speed is inversely proportional to time. Algorithm A and B were measured doing the same job, we could define the speeds

  • SA = 1 job / 8.26789 seconds = 0.12095 jobs/sec
  • SB = 1 job / 814.21416 seconds = 0.0012282 jobs /sec

Now let's think of two cars, one goes a certain distance at 55 miles/hour while the other one goes at 50 miles/hour, we would say the faster car is

  • 10% faster = ((55 mph/50 mph)-1) x 100%.

Applying that formula to your algorithms,

  • ((SA / SB)-1) x 100%
  • = ((0.12095 jobs/sec / 0.0012282 jobs/sec)-1) x 100%
  • = (98.48 - 1) x 100%
  • = 9747 %

The two algorithms are so different in speed (almost a factor of 100) that percent faster is probably not the best way to compare them. It would be better to say A is x times faster than B:

  • A is X times faster than B
  • X = SA / SB
  • X = 98.48

Algorithm A is 98.48 x faster than B.

For a discussion on this subject in Mathematics Stack Exchange see here.

Upvotes: 2

Related Questions