CODEWITHSUNDEEP
algorithmperformancesortingruntimebig-o
User
User

Reputation: 1726

How do these results prove my method is running in O(n lgn) time?

I have a method that I wrote below.

public static long nlgn(double[] nums)  {

        long start = System.nanoTime();

        if(nums.length > 1)     {
            int elementsInA1 = nums.length/2;
            int elementsInA2 = nums.length - elementsInA1;
            double[] arr1 = new double[elementsInA1];
            double[] arr2 = new double[elementsInA2];

            for(int i = 0; i < elementsInA1; i++)
            arr1[i] = nums[i];

            for(int i = elementsInA1; i < elementsInA1 + elementsInA2; i++)
            arr2[i - elementsInA1] = nums[i];

            nlgn(arr1);
            nlgn(arr2);

            int i = 0, j = 0, k = 0;

            while(arr1.length != j && arr2.length != k) {
                if(arr1[j] <= arr2[k]) {
                    nums[i] = arr1[j];
                    i++;
                    j++;
                } else {
                    nums[i] = arr2[k];
                    i++;
                    k++;
                }
            }

            while(arr1.length != j) {
                nums[i] = arr1[j];
                i++;
                j++;
            }
            while(arr2.length != k) {
                nums[i] = arr2[k];
                i++;
                k++;
            }
        }

        double max = nums[nums.length - 1];
        double min = nums[0];

        double[] farthestPair = {max, min};

        long end = System.nanoTime();

        return (end - start);
    }

This is basically a merge sort operation that, once sorted, will find the smallest and largest numbers. I believe this method is operating in O(n lgn) time. However, when I run the function with an input size that doubles upon each run (1000, 2000, 4000, etc.), I get the following results when I time it in nano time.

First pass: (0.12) seconds
Second pass: (0.98) seconds
Third pass: (0.91) seconds
Fourth pass: (0.90) seconds
Fifth pass: (1.33) seconds

My question is, given these results, do these results suggest that this method is running in O(n lgn) time?

Upvotes: 0

Views: 74

Answers (1)

Toro
Toro

Reputation: 41

If you have the source code of the algorithm, you should analyze it instead of doing runtime benchmarks.

In the case of recursive functions, take a look to the master theorem.

In your function you do 2 recursive calls with size n / 2, so a = 2, b = 2 and f(n) = 2n, because in your two first for loops you iterate along all the array (n) and with the three final while loops you iterate again all the array size (n), so 2n.

If you apply the master theorem it gives you as result Θ(n ln(n)), so O(n ln(n)) is correct too.

Upvotes: 1

Related Questions