Hi everyone,
I came across below problem and here's my take on it. Can we discuss the solution?
Problem statement (AS IS): Write a
java program to find out the first three highest numbers of the integer array in descending order. Explain the time complexity of your solution (Big O Notation)
Time Complexity of
getArray method:
No. of elements in the array is N and no. of elements to be returned is K.
- Assume that (Arrays.sort(a);) uses Merge/quick sort, O(N logN)
- for loop, O(K)
- result[j] = a[i];
-- a[i],access of array is constant, O(1)
-- result[j], insertion in array, O(K)
O(N logN) + O(K) + O(1) + O(K)
= O(N logN + 2K)
= O(N logN + K) (Drop the constant)
= O(N logN) (for very small values of K)
Does this sound right? Thank you