Is the running time the same as O (nlogn)?

Question

I wrote a class (greedy strategy) that first used a sorting method that has O (nlogn)

Collections.sort (array, new SortingObjectsWithProbabilityField ());

and then I used the insert method binary search tree, which takes O(h)andh here is the tree height.

for different n, the runtime will be:

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

which I think is wrong, because in order to increase n, the operating time should almost increase.

This method will take some 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

Answer 1

, , nlogn, . , , n logn . , n = 513 logn 9.003.

, , , . , ( 10, 100, ) (5 - ), . / n, , . , , .

n 2. 1, 2, , - .

, gnuplot script :

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

Answer 2

. , , .

, K (, K 17, K 33 ) (, K = 100)

, . nlog (n) , , , , . , ...