What is the time-complexity of a program that finds the length of the longest consecutive sequence in an array of integers?

Question

Can somebody explain to me what the time-complexity of this program is?

public static void main(String[] args) {
    int arr[] = { 1, 9, 3, 10, 4, 20, 2};
    ConsecutiveSequence(arr);
}

public static void ConsecutiveSequence(int []a){
    Arrays.sort(a);

    int k =1;
    int n = a.length;
    int max_length=0;
    
    for(int i =0;i<n-1;i++){
        if(a[i]+1==a[i+1]){
            k++;
            if(i==n-2){
                max_length=Math.max(max_length,k);
            }
        }else{
            max_length=Math.max(max_length,k);
            k=1;
        }
    }

    System.out.println(max_length);
}

dreamcrash · Accepted Answer · 2021-02-11T11:40:35.873

The time complexity is N log (N). Why?

Arrays.sort(a);

for(int i =0;i<n-1;i++){
    if(a[i]+1==a[i+1]){
        k++;
        if(i==n-2){
            max_length=Math.max(max_length,k);
        }
    }else{
        max_length=Math.max(max_length,k);
        k=1;
    }
}

The operation:

Arrays.sort(a);

has a well-know complexity of N log (N). As one confirm here:

This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

For the loop you iterative n-1 times and for each iteration you performance constant operations. So (N-1) * C.

So the overall complexity is N log (N) + (N - 1) * c. Since with increment of the input N log (N) grows much faster than (N - 1), the complexity can be represented by O(N log (N)). For more information on why it can be represented by O(N log (N)) have a look at this SO Thread.

What is the time-complexity of a program that finds the length of the longest consecutive sequence in an array of integers?

1 Answers1