CODEWITHSUNDEEP
javaalgorithmsortingtime-complexity
Yosvanys Aponte
Yosvanys Aponte

Reputation: 51

What is the time complexity for this sort algorithm?

Explaning better

I have the following problem, I have source array of integer values, then I need to order the source array by suffix comparator and put it a sorted array, The problem is that I want to know which is the time complexity of constructing the suffix-array(sorting the source array)

This is the method sort:

Collections.sort(sorted, new SuffixComparator<Integer>(source));

and this is the class SuffixComparator:

public class SuffixComparator<Type extends Comparable<Type>> 
implements java.util.Comparator<Integer> {
List<Type> array1;
List<Type> array2;

/**
 * Constructor with a single array
 */
public SuffixComparator (ArrayList<Type> array) {
array1 = array;
array2 = array;
} 

/**
 * Constructor with two arrays
 */
public SuffixComparator (List<Type> a1, List<Type> a2) {
array1 = a1;
array2 = a2;
}  

/**
 * Constructor with two arrays
 */
public SuffixComparator (ArrayList<Type> a1, ArrayList<Type> a2) {
array1 = a1;
array2 = a2;
}

/**
 * Compare two suffixes 
 * @param offset1 first offset
 * @param offset2 second offset
 */
public int compare (Integer offset1, Integer offset2) {
int result;
if ( array1 == array2 && offset1.equals(offset2) ) {
    result = 0;
} else {
    int n1 = offset1;
    int n2 = offset2;
    while (n1 < array1.size() && 
       n2 < array2.size() && 
       array1.get(n1).equals(array2.get(n2))) {
    ++n1;
    ++n2;
    }
    if (n1 == array1.size()) {
    result = (n2 < array2.size()) ? -1 : 0;
    } else if (n2 == array2.size()) {
    result = 1;
    } else {    // n1 < array1.size && n2 < array2.size
    result = array1.get(n1).compareTo(array2.get(n2)); 
    }
} 
return result;
}

}

Any suggestions?

Upvotes: 4

Views: 526

Answers (3)

John Bollinger
John Bollinger

Reputation: 180103

I suppose that array1.get() and array2.get() cost O(1), and ignore the cost of computing the println() argument, which I presume is only for debugging. Collections.sort() of Java 8 performs O(n log n) comparisons on general input. (Tighter bounds may apply to inputs that initially are nearly sorted.) Typical comparison functions cost O(1), but yours appears to cost O(k), where k is the minimum of array1.size() and array2.size(). Behavior of a sort based on that comparator is thus bounded by O(nk log n).

It is conceivable that there is in fact a tighter bound on the combination of the two, but I'm not immediately seeing how that would arise.

Note, however, that under some circumstances the assumption about the cost of array1.get() and array2.get() would not hold. In particular, if one or both of the objects does not provide efficient random access (a linked list, for example), and if the sizes of these objects are not bounded by a constant, then the asymptotic performance is worse.

Upvotes: 5

Nirmal Dhara
Nirmal Dhara

Reputation: 2141

If your code execute the if block then complexity is O(1).

if your code execute the else block then the complexity is O(n1xn2)+ O(logn).

Here n1= length of array1 n2 = length of array2.

so complexity will be O(n1xn2)+O(logn)

Upvotes: -1

Frederic Lachasse
Frederic Lachasse

Reputation: 721

We have 3 arrays there: sorted, array1 and array2. The complexity of the sort operation is related to the sorted array, not the compare operation. So it has the complexity of the Collections.sort() method, which AFAIK is O(n log n), n being the size of the sorted array. The "complexity" of the compare function is not going to change any of that.

So what is the problem exactly?

Upvotes: -2

Related Questions