4

I'm working on finding the max pairwise product of an array algorithm as practice. I've been able to get it down to 2n comparisons, by finding the largest and second largest numbers in the array using two seperate for loops. I know i could get it down even farther if I sorted then compared.

In the algorithm below is it n comparisons? I only have 1 loop so I'm assuming it is. also, what would be the Big O number for this? Is it the same as the number of comparisons? I know that we remove any constants if there is a variable and take the largest degree of the problem [sorry for the unclear explanations of algorithms -I'm just beginning on this.

static int EvenFasterAlgorithm (int[] numbers) {
        int maxNum1, maxNum2, index, index2;
        maxNum1 = -1;
        maxNum2 = -1;
        index = -1;
        index2 = -2;
        System.out.println("the size is "+ numbers.length);
        int k = numbers.length-1;

        if(numbers.length > 1)
        {
        for(int i = 0; i < numbers.length; i++) {

            if(numbers[i] > maxNum1 && i != index2) {
                maxNum1=numbers[i];
                index = i;

            }

            if(numbers[k] >= maxNum2 && k != index)
            {
                maxNum2 = numbers[k];
                index2 = k;

            }
            k--;
        }
        return maxNum1*maxNum2;
        }
        else
        {
            return numbers[0];
        }
    }
Katie Melosto
  • 1,047
  • 2
  • 14
  • 35
  • 1
    If you want to know how many comparisons you have, *count them*. – Prune Jan 02 '20 at 22:34
  • 2
    Sorting costs more than 2N comparisons. Your algorithm as described is asymptotically optimal. – Louis Wasserman Jan 02 '20 at 22:37
  • 1
    The procedure as described may produce the wrong result (try [-2, -1, 0, 9]). As such, it does *not* constitute an algorithm for the problem sketched. Which has been discussed here time and again (if more often using three factors). – greybeard Jan 02 '20 at 22:46
  • 1
    (I think this is not a duplicate for asking about correctness of time complexity assessment, not *best* algorithm.) – greybeard Jan 02 '20 at 22:58
  • 1
    You only have 1 loop, but the loop body contains at least 2 comparisons: `numbers[i] > maxNum1` and `numbers[k] >= maxNum2`, and arguably has 4 comparisons if you count `i != index2` and `k != index`. And that's ignoring the loop condition itself, i.e. `i < numbers.length`. So the code has between 2N and 5N comparisons, depending on how you count them. Of course, big-O doesn't care about constant multipliers, so the algorithm is O(N). – user3386109 Jan 02 '20 at 23:37

0 Answers0