1

I am trying to design an algorithm with O(1) time complexity that returns a value from an array that isn't the smallest value. I understand that searching the array and comparing its elements to find the smallest will make the algorithm O(n), so that wouldn't work.

If I write a separate method that uses a sorting algorithm to sort the array first and then return the smallest, will this effect the time complexity of the algorithm?

Here's my code:

private static int nonSmallestElement(int[] array) {
    int smallest = smallestElement(array);
    int index = (int) (array.length * Math.random());
    System.out.println("Index = " + index);
    for (int i = index; i < array.length; i++) {
        if (array[i] != smallest) {
            return array[i];
        }
    }
    return array[1];
}

private static int smallestElement(int[] array) {
    Arrays.sort(array);
    return array[0];
}

Here the Arrays.sort() method is using a Dual-Pivot Quicksort algorithm, which is O(n log(n)). Does this now mean that the nonSmallestElement() method takes on that time complexity as well, or is it O(1) because it doesn't have to handle the sort?

Bohemian
  • 412,405
  • 93
  • 575
  • 722
PumpkinBreath
  • 831
  • 1
  • 9
  • 22
  • You have to count the sort, otherwise you are cheating. But why do you want to sort the array anyway? I thought you wanted to return an element that was **NOT** the smallest. – President James K. Polk Nov 07 '18 at 01:10
  • Hi. In order to make sure that I am not returning the smallest value I would have to know what the smallest value was wouldn't I? And then do a comparison to return any other value != smallest – PumpkinBreath Nov 07 '18 at 01:14
  • To find smallest value you do not need to sort the array. Sorting is at least O(nlogn), but finding smallest element can be done in O(n). – uli Nov 07 '18 at 01:16
  • 2
    Here is a hint: if you have in hand two **distinct** values, then the larger one must not be the smallest value in the array. For a "typical" array you'd expect to find two distinct value in the any two elements. – President James K. Polk Nov 07 '18 at 01:16
  • 1
    @JamesKPolk I believe I'm with you. That way I can just compare any 2 elements and return the one that's bigger. Cheers – PumpkinBreath Nov 07 '18 at 01:21
  • 1
    @PumpkinBreath - if you can have non-distinct (equal) values, then you may have to look through more than 2. – moreON Nov 07 '18 at 01:24
  • If it's an hour by train from point A to point B, and 10 hours by car from my house to the train station at point A, I can't fairly say it's an hour's trip from my house to point B, can I? Same principle applies to time complexity when compounding algorithms. – Kevin Anderson Nov 07 '18 at 01:54

1 Answers1

1

You are right you need to count all actions to calculate complexity of the algorithm. But you should be aware of the rules, for example bigger one includes smaller (more examples). In your case you are calling smallestElement() once - O(nlogn) and than have a loop O(n). As result overall complexity will be O(n + nlogn). But final complexity of the nonSmallestElement() is O(nlogn) because nlogn is bigger.

On other side it is not possible to have algorithm better than O(n) to return not min value. Because you will need to iterate over all elements at least once to find minimum. Exception could be sorted array.

Update from comments:

Here is a hint: if you have in hand two distinct values, then the larger one must not be the smallest value in the array. For a "typical" array you'd expect to find two distinct value in the any two elements. @James K Polk

uli
  • 671
  • 6
  • 15