Find the three largest elements in an array

Question

Sample input: [141, 1, 17, -7, -17, -27, 18, 541, 8, 7, 7]

Sample output: [18, 141, 541]

My Code

class Program {
     public static int[] findThreeLargestNumbers(int[] array) {
       int j = array.length;
       while(j>= array.length-3){
           for(int i = 0; i<j-1; i++){
               if(array[i]>=array[i+1]){
                   int temp = array[i];
                   array[i] = array[i+1];
                   array[i+1] = temp;
               }
           }
           j--;
       }
       int [] result = new int [3];
       result[0] = array[array.length-3];
       result[1] = array[array.length-2];
       result[2] = array[array.length-1];
       return result;
    }
}

I figured I can do bubble sort "3" times since I only care about the 3 largest elements and then exit. I know a traditional bubble sort algorithm is O(N^2). However does my modified algorithm have a better time complexity of O(N) since my while loop only runs 3 times and my for loops runs for N elements making is O(3N) hence O(N) ??

I just need help understanding the time complexity on this rather than the solution which is quite easy.

Answer 1

Yes, you are right, your algorithm makes about 3N comparisons and has O(N) complexity.

It is better than full bubble sort because algo performs only partial sorting, the rest remains unsorted.

But note that complexity is linear for fixed number of largest elements (here 3). If you need to select say n/3 largest ones - this approach becomes quadratic, and you'd rather choose another kind of partial sorting (for example, algo based on Quicksort partition or binary heap one)