CODEWITHSUNDEEP
javatime-complexity
Stoud
Stoud

Reputation: 293

Time Complexity of kth largest

So I was asked to find the kth largest value in an array. The code is in java as the tag suggests. I don't fully understand time complexity, and heard this can be done in O of n. I'm wondering what the time complexity of my program would be.

Note, this method really finds the (k+1)Largest Element, and that is intentional.

public static int kthLargest(int[] a, int k){
    int max = Integer.MAX_VALUE, curMax;

    for (int i = 0; i <= k; i++){ //Recurs k+1 times. 
        curMax = 0;

        //This loop just finds the max of the input array.
        //It also makes sure that the max it is finding is less 
        //than the previous max found.
        for (int j = 0; j < a.length; j++){ 
            int num = a[j];
            if (num > curMax && num < max){
                curMax = num;
            }
        }

        max = curMax;
    }
    return max;
}

Just a note, my guess is that it would be O of k*n, which would be worst case of n^2 iterations, however someone told me that k did not matter.

Upvotes: 2

Views: 372

Answers (3)

Jahangir Ali
Jahangir Ali

Reputation: 55

If you are using asymptotic notations to represent time complexity, you can ignore the constants, as by default the meaning of O(n) is g(n) <= cf(n) there g(n) is your function.

The time complexity of your program is O(kn) and yes it can be done in O(n) or O(k*log n).

Try this: https://en.wikipedia.org/wiki/Search_algorithm

Upvotes: 0

ryanbwork
ryanbwork

Reputation: 2153

Time complexity can be a meaty topic, so for the sake of your question lets just define O as the maximum amount of time a given algorithm will take, expressed in the number of operations (usually comparisons) required.

So, traversing an array of size N and finding the largest element takes O(N), because we're having to compare each element in the array to the largest element we've seen up to this point; we only need to traverse the array once while storing the current largest element in memory, hence O(N).

Let's say we then wanted to traverse the same array again, but this type we wanted to find number of elements that are > the current element, for each element in the array. In this case, you'd traverse the full array once for each element in the array, effectively visiting each element N times. N elements in the array visited N times is N*N, so this algorithm would be O(N^2).

Your algorithm finds the max number in the array K times, where K is the Kth greatest value in the array (I'm assuming you know how the given code works). K, or C, is often used to define a constant in O notation. In some cases, like when multiplying or adding to a polynomial, constants are discarded when defining the O for a given algorithm, though in this case it makes sense to retain the constant due to its non-negligible effect.

Do a simple google search for solutions to this problem that run in O(N) time.

Upvotes: 1

Louis Wasserman
Louis Wasserman

Reputation: 198163

Yes, you're correct that your algorithm is O(k*n), and that there is an O(n) algorithm that is not your algorithm.

(It sounds like your problem is homework, so it's not clear to me I should give you the best answer, but one simple solution might be to sort the array and take the kth element from the end.)

Upvotes: 1

Related Questions