1

I have read about time complexities only in theory.. Is there any way to calculate them in a program? Not by assumptions like 'n' or anything but by actual values..

For example.. calculating time complexities of Merge sort and quick sort..

Merge Sort= O(nlogn);// any case

Quick Sort= O(n^2);// worst case(when pivot is largest or smallest value)

there is a huge difference in nlogn and n^2 mathematically..

So i tried this in my program..

main()
    {
       long t1=System.nanoTime();
       // code of program..
       long t2=System.nanoTime();
       time taken=t2-t1;
    }

The answer i get for both the algorithms,in fact for any algorithm i tried is mostly 20.

Is System.nanoTime() not precise enough or should i use a slower system? Or is there any other way?

Shubh
  • 6,693
  • 9
  • 48
  • 83
Shashank Raghunath
  • 149
  • 3
  • 15
  • t1 is at the start of main() and t2 is at the end of main(). – Shashank Raghunath Jun 03 '13 at 09:31
  • How many values have you used? – pad Jun 03 '13 at 09:33
  • i tried it with some 50-100 values.. same result. – Shashank Raghunath Jun 03 '13 at 09:42
  • 3
    50-100 is not a large enough test case for O(n^2) or O(n log n). You could try a bunch of values for n - 10,100,1000,10000,100000,1000000. And typically you want to run it a few times in a row between recording the start and end times to get more accurate results. And quick-sort is average case O(n log n), thus you can expect similar times from quick-sort and merge sort, unless you're testing the pathological cases. – Bernhard Barker Jun 03 '13 at 10:25

7 Answers7

4

Is there any way to calculate them in a program? Not by assumptions like 'n' or anything but by actual values.

I think you misunderstand what complexity is. It is not a value. It is not even a series of values. It is a formula. If you get rid of the N it is meaningless as a complexity measure (except in the case of O(1) ... obviously).

Setting that issue on one side, it would be theoretically possible to automate the rigorous analysis of complexity. However this is a hard problem: automated theorem proving is difficult ... especially if there is no human being in the loop to "guide" the process. And the Halting Theorem implies that there cannot be an automated theorem prover that can prove the complexity of an arbitrary program. (Certainly there cannot be a complexity prover that works for all programs that may or may not terminate ...)

But there is one way to calculate a performance measure for a program with a given set of input. You just run it! And indeed, you do a series of runs, graphing performance against some problem size measure (i.e. an N) ... and make an educated guess at a formula that relates the performance and the N measure. Or you could attempt to fit the measurements to a formula.

However ...

  • it is only a guess, and
  • this approach is not always going to work.

For example, if you tried this on classic Quicksort, you most likely conclude that complexity is O(NlogN) and miss the important caveat that there is a "worst case" where it is O(N^2). Another example is where the observable performance characteristics change as the problem size gets big.

In short, this approach is liable to give you unreliable answers.

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
2

Well, in practice with some assumptions on the program, you might be able to run your program on large number of test case (and measure the time it takes) and use interpolation to estimate the growth rate and the complexity of the program, and use statistical hypothesis testing to show the probability you are correct.

However, this thing cannot be done in ALL cases. In fact, you cannot even have an algorithm that tells for each program if it is going to halt or not (run an infinite loop). This is known as the Halting Problem, which is proven to be insolveable.

amit
  • 175,853
  • 27
  • 231
  • 333
1

Micro benchmarks like this are inherently flawed, and you're never going to get brilliantly accurate readings using them - especially not in the nanoseconds range. The JIT needs time to "warm up" to your code, during which time it will optimise itself around what code is being called.

If you must go down this route, then you need a big test set for your algorithm that'll take seconds to run rather than nanoseconds, and preferably a "warm up" period in there as well - then you might see some differences close to what you're expecting. You're never going to just be able to take those timings though and calculate the time complexity from them directly - you'd need to run many cases with different sizes and then plot a graph as to the time taken for each input size. Even that approach won't gain you brilliantly accurate results, but it would be enough to give an idea.

Michael Berry
  • 70,193
  • 21
  • 157
  • 216
1

Your question might be related to Can a program calculate the complexity of an algorithm? and Program/algorithm to find the time complexity of any given program, I think that you do a program where you count while or for loops and see if its nested or not but I don't figure how you can calculate complexity for some recursive functions.

Community
  • 1
  • 1
Mihai8
  • 3,113
  • 1
  • 21
  • 31
1

The microbenchmark which you wrote is incorrect. When you want to gather some time metrics of your code for further optimization, JFF, etc. use JMH. This will help you a lot.

pbespechnyi
  • 2,251
  • 1
  • 19
  • 29
1

When we say that an algorithm exhibits O(nlogn) complexity, we're saying that the asymptotic upper bound for that algorithm is O(nlogn). That is, for sufficiently large values of n, the algorithm behaves like a function n log n. We're not saying that for n inputs, there will definitely be n log n executions. Simply that this is the definition set, that your algorithm belongs to.

By taking time intervals on your system, you're actually exposing yourself to the various variables involved in the computer system. That is, you're dealing with system latency, wire resistance, CPU speed, RAM usage... etc etc. All of these things will have a measurable effect on your outcome. That is why we use asymptotics to compute the time complexity of an algorithm.

christopher
  • 26,815
  • 5
  • 55
  • 89
1

One way to check the time complexity is to run both algorithms , on different sizes of n and check the ratio between each run . From this ratio you can get the time complexity

For example
If time complexity is O(n) then the ratio will be linear

If time complexity is O(n^2) the ratio will be (n1/n2)^2
if time complexity is O(log(n)) the ratio will be log(n1)/log(n2)

Mzf
  • 5,210
  • 2
  • 24
  • 37