Java – does the runtime match o (nlogn)?

I wrote a class (greedy strategy). At first, I used the sorting method with O (nlogn)

Then I used the binary search tree insertion method, which takes O (H), where h is the tree height

For different N, the run time will be:

n,running time
17,515428
33,783340
65,540572
129,1285080
257,2052216
513,4299709

I don't think this is correct, because increasing N, the running time should almost increase

This method will take running time:

Exponent = -1;



for(int n = 2;n<1000;n+=Math.pow(2,exponent){

     for (int j = 1; j <= 3; j++) {
                Random rand = new Random();
                for (int i = 0; i < n; i++) {
                    Element e = new Element(rand.nextInt(100) + 1,rand.nextInt(100) + 1,0);
                    for (int k = 0; k < i; k++) {
                        if (e.getDigit() == randList.get(k).getDigit()) {
                            e.setDigit(e.getDigit() + 1);
                        }
                    }
                    randList.add(e);
                }
                double sum = 0.0;

                for (int i = 0; i < randList.size(); i++) {
                    sum += randList.get(i).getProbability();
                }
                for (Element i : randList) {
                    i.setProbability(i.getProbability() / sum);
                }
                //Get time.
                long t2 = System.nanoTime();
                GreedyVersion greedy = new GreedyVersion((ArrayList<Element>) randList);
                long t3 = System.nanoTime();
                timeForGreedy = timeForGreedy + t3 - t2;
            }
            System.out.println(n + "," + "," + timeForGreedy/3 );
            exponent++;
            }

thank you

Solution

Your data seems to roughly match the order of nlogn, as shown below Note that the curve is almost linear because logn is very small for a large value of n For example, for a maximum of n = 513, logn is 9.003

There are some ways to achieve more accurate timing, which may make the curve better adapt to the data points For example, take a larger random input sample (I recommend at least 10100, if possible) and run multiple iterations per data set (5 is an acceptable number) to eliminate the inaccuracy of the timer You can use a single start / stop timer to calculate the time of all iterations for the same N, and then divide by the number of runs to obtain more accurate data points Just make sure you generate all the datasets first, store them all, and then run them

Sampling n to the power of 2 is a good choice You may just want to subtract 1 to make them accurate to the power of 2, rather than it will have any real impact

As a reference, this is the gnuplot script used to generate the graph:

set terminal png
set output 'graph.png'
set xrange [0:5000000]
set yrange [0:600]
f1(x) = a1*x*log(x)/log(2)
a1 = 1000
plot 'time.dat' title 'Actual runtimes',\
    a1*x*log(x)/log(2) title 'Fitted curve: O(nlogn)
fit f1(x) 'time.dat' via a1