Menu
Note that I don't have a "problem" and I'm not looking for "another way to find the big O of my algorithm".
What I'd like to know is if it would be possible write a program to which you'd pass data points that would all be perfs measurements of an algorithm for various input size: (n,time taken to solve problem for n) and that would then determine the complexity of your algorithm.
For example here's what the input could be (it could be much larger, it's really just an example, that's not the point of the question):
36 000 took 16 ms
109 000 took 21 ms
327 000 took 68 ms
984 000 took 224 ms
2 952 000 took 760 ms
8 857 000 took 2305 ms
26 571 000 took 7379 ms
79 716 000 took 23336 ms
Using such kind of data, is it possible to write a program that would tell if we have, say, an O(n), log(n), n log(n) or n! algo?
654
To express the time complexity of an algorithm, we use something called the “Big O notation”. The Big O notation is a language we use to describe the time complexity of an algorithm. It's how we compare the efficiency of different approaches to a problem, and helps us to make decisions.
In this notation an algorithm in which the primary logic is executed N2 times for a problem of size N is said to have order N2, or O(N2). It should also be realized that for a given problem there is an order of complexity for the worse case and average case of complexity.
It's running time does not depend on value of n, like size of array or # of loops iteration. Independent of all these factors, it will always run for constant time like for example say 10 steps or 1 steps. Since it's performing constant amount of steps, there is no scope to improve it's performance or make it faster.
The running time of an algorithm refers to the length of time it takes for it to run as a function. An algorithm's running time for a given input depends on the number of operations executed. An algorithm with more operations will have a lengthier running time.
What you are looking for is Curve fitting. All the simple algorithms for this problem that I know of will try to fit the data points into some sort of polynomial, but I suspect there're those that will be able to differentiate between polynomials and non-polynomials too.
128
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
