Finding the maximum and minimum using less than O(2n) time

Given an array of integers, find the maximum and minimum of the array. It seems trivial to find the maximum or the minimum. Let n be the length of the array.

O(2n) 
Using n - 1 comparisons, we are able to find the maximum. With another n - 1 comparisons, we are able to find the minimum. In order to find the minimum and maximum, the total runtime will be O(2n).

Could we do better?

How about sort the array first? Using the fastest sorting algorithm,  the time complexity will be O(nlogn), which is more expensive than O(2n).

Actually, there is an algorithm with O(1.5n) time complexity.

This is how it works. We uses two variables curMax, curMin to keep track of the current maximum when we iterate through the array. The most important point is that each iteration, we will inspect two numbers in the array. Let's name them A and B. We compare A and B first. Then, we compare the larger one with the curMax, and update the curMax if necessary. Also, we compare the smaller one with curMin and update the curMin if necessary. For these two numbers, we do three comparisons. Since there are n numbers in the array, the total comparisons will be n / 2 * 3 = 1.5n.

Comments

Post a Comment

Popular posts from this blog

Can I name a method with the same name of the class in Java?

Can a class have a method with the same name of the class in Java? The answer is yes. See the example below. Public class MyClass { public MyClass() { } public void MyClass() { System.out.println("I have the same name as the class!"); } } You could definitely name a method with the name of the class. As a rule of thumb, you should not capitalize the first letter of the name of your method, though.
Read more

What is new in Java 8

1.  There are default methods and static methods in interfaces in Java 8. 2. Lamdas   Collections . sort ( list , ( o1 , o2 ) -> o1 . getTime () - o2 . getTime ()); Pre-Java8 Collections . sort ( list , new Comparator < Message >() { @Override public int compare ( Message o1 , Message o2 ) { return o1 . getTime () - o2 . getTime (); } });
Read more

Quicksort Java implementation

import java.util.Arrays; public class QuickSort { int [] data ; public void quicksort( int [] nums) { if (nums == null || nums. length == 0 ) return ; data = nums; sort( 0 , nums. length - 1 ); } private void sort( int left, int right) { if (right <= left) return ; int pivot = partition(left, right); sort(left, pivot - 1 ); sort(pivot + 1 , right); } /** * put all the numbers that are smaller than pivot to the left * **/ int partition( int left, int right) { int pivot = data [right]; int startIndex = left; for ( int i = left; i < right; i++) { //all the nums on the left of startIndex are smaller than pivot //the number at startIndex is >= pivot if ( data [i] < pivot) { swap(startIndex++, i); } } // put the pivot to the right position swap(startIndex, right); r...
Read more