2

I'm trying to compare two algorithms and their Big Oh efficiencies. I am trying to find the value for n where one algorithm becomes more efficient than the other algorithm. Any helpful examples or resources would be a huge help.

Patrick Hession
  • 45
  • 6
  • 1
    Big-O tells you nothing about this - the `n` doesn't represent a parameter that you can plug in a value for. – Oliver Charlesworth Nov 25 '17 at 16:39
  • 1
    Do benchmarks. Precise math does not work since computers differ a lot... – Fureeish Nov 25 '17 at 16:39
  • You can get a value for n from the definition of Big Oh – Patrick Hession Nov 25 '17 at 16:45
  • @PatrickHession Please edit your question to include a more detailed description of what you are trying to do. – Progman Nov 25 '17 at 17:48
  • I have to compare the Karatsuba runtime with the long multiplication runtime using Big Oh notation and then find at what value of n that the Karatsuba multiplication outperforms the long multiplication. – Patrick Hession Nov 25 '17 at 19:21
  • @PatrickHession When you have the two functions you can simply build an inequality and solve it for `n`. Anyway, this is more like a math problem and not a java/programming problem. – Progman Nov 25 '17 at 22:13

1 Answers1

1

You really need to know more than just the BigO complexity of an algorithm in order to determine exactly at what point one algorithm becomes more efficient than another, assuming that they have different lower order terms and constants and that the one that has worse BigO characterics has better lower order terms\constants. But usually the approximation is enough.

Runtime complexity of algorithms is the tool to use when dealing with problems of growing scale of input size.

Empirical performance profiling is the tool to use when dealing with high frequency, repetitive problems that generally involve small inputs*

(*) What constitutes small inputs depends on the complexity of the algorithms involved. For example, for the travelling salesman problem, an input of size 5 is small while an input of size 15 is huge. For sorting, 20 elements would be considered small, 20000 large and 2000000 would be huge.

Mike Dinescu
  • 54,171
  • 16
  • 118
  • 151