Big-O notation of a function in Java by experiment

Question

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

This appears to be a homework. If it is, well, you are expected to figure out the solution by yourself. You likely were given the knowledge to do this. If you don't know where to start, then try harder. — Stefano Sanfilippo, Oct 28 '14 at 22:48
what ????? i have never heard of program that can determines big oh. Thats analysis you have to perform yourself by running the algorithm with different inputs — Chiseled, Oct 28 '14 at 22:49
@Moh123 That's not an analysis, that's a simulation. An analysis requires math. — chrylis -cautiouslyoptimistic-, Oct 28 '14 at 22:51
You can start by explaining the [Halting Problem](https://en.wikipedia.org/wiki/Halting_problem) to whoever came up with this idea. Also, the Big-O notation values are always parametrized with *something*. How do you determine that "something" without knowing anything about the algorithm/program? — mikołak, Oct 28 '14 at 22:53

Stephen C · Accepted Answer · 2014-10-29T01:48:10.187

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.

Yeah, that's what i'm trying to do. But, how i fit the experimental results whith the diferent types of curves automatically? — Ismael Esteruelas Regalado, Oct 28 '14 at 23:00

score 0 · Answer 2 · answered Oct 28 '14 at 22:47

0

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.

answered Oct 28 '14 at 22:47

Dko

820
6
12

That's what i'm doing now, but i need to determine it automatically – Ismael Esteruelas Regalado Oct 28 '14 at 22:49
there is no way to do it automatically – Chiseled Oct 28 '14 at 22:51
refer to this post http://stackoverflow.com/questions/9958299/a-tool-for-calculating-the-big-o-time-complexity-of-java-code – Chiseled Oct 28 '14 at 22:51

score 0 · Answer 3 · answered Oct 28 '14 at 22:51

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.

Big-O notation of a function in Java by experiment

3 Answers3