4

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?

Improve this question
3
  • 1) Where is array1 and array2 coming from? 2) From the javadoc for Collection.sort(): "a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted" Commented May 8, 2015 at 15:37
  • What is array1 and array2 ? and how do you call your sort ? Commented May 8, 2015 at 15:37
  • this sort method is for sorting an array for constructiion of a suffix array Commented May 8, 2015 at 16:26

3 Answers 3

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I'd better say about O(KN logN) where K is length of array1 or array2 (since we still don't know where they do come from)
-1

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)

Improve this answer

8 Comments

O(n1 * n2) means some nested loop, don't it?
can you tell me why System.out.println(array1.get(offset1) + " " + array1.get(2)); if ( array1 == array2 && offset1.equals(offset2) ) { it means array1 and array2 are there. if some one only thinks about documents and do not calculate anything for this code, ..
Yes it is for nested loop, code is comparing the array1 and array2
@NirmalDhara array1 == array2 compares references, not content.
@Sasha Salauyou what is array2.get(n2).
|
-2

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?

Improve this answer

5 Comments

"The complexity of the sort operation is related to the sorted array, not the compare operation": that's simply not so. The sort operation involves performing the compare operation (usually many times), so the time complexity of the two cannot be separated.
"The "complexity" of the compare function is not going to change any of that"--in which magic way it is not?
The complexity is relative to a size parameter. So is it n size of sorted, n1 size of array1 or n2 size of array2? If n, then what counts is the number of time the compare function is called, not the average time you need for a compare, i.e. O(n log n) is the same as O(K*(n log n))
Then if what is important is the compare function, then the question should be what is the complexity of the compare relative to n1 or n2, not the the sort itself, and that looks like O(n) to me. And if there is a relation between n and n1 or n2 (around same size?), then it is not apparent in the question, so cannot five a proper answer
If K is constant, O(nlogn) is right assumption. If K also determines input data (ie may vary), O(kn log n) is more correct.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.