Hi

I have written a class(greedy strategy) that at first i used sort method which has O(nlogn)

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

and then i used the insert method of binary search tree which takes O(h) and h here is the tree height.

for different n ,the running time will be :

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

which I think is not correct because for increasing n , the running time should almost increase.

This method will take the 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++;
            }

thanks