stretchr
stretchr

Reputation: 615

How to know complexity of finding kth largest element in specific implementation

I am trying to teach myself order statistics by solving the problem

find the kth largest element in an array in O(n) time.

My Java implementation is as follows below.

Qn: I am unsure of how to determine the complexity of my code. From what I understand, it does not exceed n. Is this correct? Or how should I get this?

Have adapted the algorithm from pg 215, Intro to Algo MIT Press.

package intp;

public class IntP {
    public static void main(String[] args) {
        int[] qn = {10,22,33,4,5,6,1};
        int[] res = {0,0};
        int q;
        int k =3;
        q=k;
        while (k>=1){
        res = findMax(qn,k);
        qn[res[1]]=0;
        k=k-1;
        }        
        System.out.println("Largest element number "+q+ " is: "+res[0]);
    }
    public static int[] findMax(int[] a,int k){
        int pos=0;
        int max = a[0];
        int[] ans= {0,0};
        for(int i= 1;i<a.length;i+=2){
            if (i+1==a.length){
                if (a[i]>max){
                    max=a[i];
                   pos=i;
                }
                break;
            }            
            if (a[i]>a[i+1] && a[i]>max){
                max=a[i];
                pos=i;
            }
            else if (a[i+1]>max && a[i+1]>max){
                max= a[i+1];
                pos=i+1;
            }            
        }
        ans[0]=max;
        ans[1]= pos;
        return ans;
    }
}

Upvotes: 0

Views: 269

Answers (2)

user1196549
user1196549

Reputation:

Repetitive selection of the maximum is a poor way to implement selection of the Kth (except maybe for very small K). It takes worst-case time O(KN).

A better approach is to sort the array, for example using Quicksort, performing in expected O(N.Lg(N)). Anyway, the worst-case time is quadratic, O(N²).

A bit better, Quickselect, a "stripped-off" version of Quicksort. Closer to linear time O(N), but it keeps the worst-case O(N²).

The truly optimal approach (in the asymptotic sense) is that of the Median of Medians, with a guaranteed O(N) behavior.

My preferred implementation of the naïve approach:

for (i= 0; i < n; i++) // Try every element a[i]
{
  int r= 0;
  for (j= 0; j < n; j++) // Evaluate the rank by counting inferior elements
  {
    r+= a[j] < a[i] || (a[j] == a[i] && j < i); // Mind the equal elements
  }

  if (r == k) // Desired rank
    return i;
}

Upvotes: 0

Khaled.K
Khaled.K

Reputation: 5950

First Time complexity of findMax:

Time(findMax) = 3 + 1/2 n * (4 + 2) + 1 + 3

Time(findMax) = 3 n + 7

Time(findMax) ~ n

Time(findMax) ~ O(n)

Then Time complexity of main:

Time(main) = 5 + k * (3 + Time(findMax))

Time(main) = k * (3 n + 10) + 5

Time(main) = 3 k n + 10 k + 5

Time(main) ~ k * Time(findMax)

Time(main) ~ O(kn)

Note: I considered any managed instruction as 1 operation

Upvotes: 2

Related Questions