If a run an algorithm I have calculated to be O(n^2) on two different n's, all else constant, can I verify it is O(n^2) by comparing execution times? For example, n1 = 50 and n2 = 100. Since n2 is n1, time2 should be (n2 - n1)^2 times larger than time1, right? Or is verification only possible with a graph?
2 Answers
It depends on meaning of "verify".
If you mean formally verify (i.e. prove) then:
No, but both plotting or just comparing the number can give you confidence that it is O(n^2) - and it is normally easier to prove that something is true if you are already confident what the result should be, and that it is true.
The reasons you cannot prove it that way are e.g.:
- The algorithm may be slow for some inputs, and you are not triggering that. Note that "random" inputs are not ideal for such testing.
- The complexity could be 100*n+n*log(n) - you are likely to see this as O(n) if you plot it for "small" values of n.
- The complexity is normally stated for an ideal computer, whereas you run on an actual computer. Thus when timing you will see a slow-down due to running out of memory caches which shouldn't be part of the ideal complexity.
If you use "verify" to mean "experimentally test" that e.g. an O(n^2) algorithm is in fact O(n^2), then, yes you can do that with both methods.
1 Comment
Personius
Thanks, I mean "verify" to mean experimentally test. I had already formally proven the complexity, but was required to show quantitative "proof", as well.
Can I verify it is O(n^2) by comparing execution times?
No.
Time complexity is pure theoretical concept. You cannot directly establish relation between execution times and time complexity .
To verify if an algorithm is O(n^2), you should be dependent only on the algorithm itself.
answered Sep 11, 2018 at 4:36
Shridhar R Kulkarni
7,1563 gold badges40 silver badges64 bronze badges
3 Comments
ChatterOne
That's kind of debatable. The whole idea of time complexity is that the algorithm takes more time to execute. It's a bit pointless to use one run with one set of data, but if you run it multiple times with different data, you'll clearly see the difference when plotting a graph of the times.
Personius
I agree that it shouldn't be relied upon, but I am required to do so for a project
Shridhar R Kulkarni
If you wish to compare two different algorithms you can compare their time complexity classes. But to verify if the algorithm is O(n^2) you must not rely on execution times. To put it other way, if you want to ask someone the time complexity of an algo, just explain them the algo. You need not write code, run it multiple times to plot execution times vs input size. Plotting the graph might give you some idea, but that cannot be accepted as a verification of time complexity of an algo.
(n2/n1)^2, not(n2-n1)^2