CODEWITHSUNDEEP
javabig-oheuristics
Ismael Esteruelas Regalado
Ismael Esteruelas Regalado

Reputation: 31

Big-O notation of a function in Java by experiment

I need to write a program that determines the Big-O notation of an algorithm in Java.

I don't have access to the algorithms code, so it must be based on experimentation and execution times. I don't know where to start.

Can someone help me?

Edit: The only thing i know about the algorithm is that takes an integer value and doesn't have a return

Upvotes: 0

Views: 388

Answers (3)

Stephen C
Stephen C

Reputation: 718936

Firstly, you need to be aware that what such a program does it to provided an evidence-based guess as to what complexity class the algorithm belongs to. It can give the wrong answer. (Indeed, in complicated cases where the complexity class is unusual, wrong answers are increasingly likely.)

In short, this is NOT complexity analysis.

The general approach would be:

  • Run the algorithm multiple times with values of N across the range, measuring the execution times. Repeat multiple times for each N, to ensure that you are getting consistent measurements.

  • Try to fit the experimental results to different kinds of curves; i.e. linear, quadratic, logarithmic. Note that it is the fit for large values of N that matters. So when you check for "goodness of fit", use a measure that gives increasing weight to the larger data points.

This is intended as a start point. For example, I'm expecting that you will do your own research on issues such as:

  • how to get reliable execution-time measurements (for Java),
  • how to do curve fitting in a mathematically sound way, and
  • dealing with the case where the execution times get too long to measure experimentally for large N.

Upvotes: 3

Hoopje
Hoopje

Reputation: 12932

Since you don't have access to the algorithm's source code, the only thing you can do is to measure how long the algorithm takes for inputs of different size, and then try to extrapolate a function from that. Since you are doing experiments, you now enter the field of statistics, so maybe you can use ideas from that area, such as regression analysis.

Upvotes: 0

Dko
Dko

Reputation: 830

You could do some experiments and graph the amount of input vs the time spent executing the function. Then you could compare it to the well known curves associated with Big-O or try to estimate the equation.

Upvotes: 0

Related Questions