lewis manuel

Ranch Hand

Posts: 64

2

posted 1 year ago

This is an assignment that I've been doing and the specifications for it are that I need to implement two methods(intersection and union) using the comparable interface(only allowed to use Java Collection API basic methods) and explain their complexity.

I've finished the first part(creating the intersection method) and described it's complexity.

The way I did it was by using a binary search on the second sort list while using a for loop for the first list so I can traverse through the first list and second list in one go. If I find a match in both sorted lists, then I add them to a list that contains all objects that are distinct and are the intersection of List 1 and List 2.

In essence, the time complexity for my method is nlogn. the n is for the for loop through the first list. The logn is because of the binary search. I don't know if it possible to make it a little bit better.

I notice that my previous code didn't check for duplicates. What I added is a variable previous that keeps track of the previous element that was found. Why I think this works is because we have a sorted list. We can have a sorted list that have duplicates like this {6, 6, 6} but not a list like this {4, 6, 4}. What this means is that the duplicate has to always be behind the element that was found previously given by the rule that we have a sorted list which or may not contain duplicates.

I've finished the first part(creating the intersection method) and described it's complexity.

The way I did it was by using a binary search on the second sort list while using a for loop for the first list so I can traverse through the first list and second list in one go. If I find a match in both sorted lists, then I add them to a list that contains all objects that are distinct and are the intersection of List 1 and List 2.

In essence, the time complexity for my method is nlogn. the n is for the for loop through the first list. The logn is because of the binary search. I don't know if it possible to make it a little bit better.

I notice that my previous code didn't check for duplicates. What I added is a variable previous that keeps track of the previous element that was found. Why I think this works is because we have a sorted list. We can have a sorted list that have duplicates like this {6, 6, 6} but not a list like this {4, 6, 4}. What this means is that the duplicate has to always be behind the element that was found previously given by the rule that we have a sorted list which or may not contain duplicates.

Piet Souris

Master Rancher

Posts: 2044

75

posted 1 year ago

You could make it a little better, although I think it is still nlogn.

Suppose your lists are A and B, and that the first element of A

equals the nth element of B. Then for the second element of A,

you only need to look at B, starting from position n + 1 (or n,

depending how you handle duplicates).

Suppose your lists are A and B, and that the first element of A

equals the nth element of B. Then for the second element of A,

you only need to look at B, starting from position n + 1 (or n,

depending how you handle duplicates).

lewis manuel

Ranch Hand

Posts: 64

2

posted 1 year ago

I've changed the intersection to look like this

Suppose if we have these sorted lists

A = {1, 2, 6, 9, 9}

B = {1, 2, 9 12}

For these two lists I would have to do four binary searches instead of five. The previous code did 5 anyways even though there is no point because you have a duplicate.

Suppose if we have these sorted lists

A = {1, 2, 6, 9, 9}

B = {1, 2, 9 12}

For these two lists I would have to do four binary searches instead of five. The previous code did 5 anyways even though there is no point because you have a duplicate.

It is sorta covered in the JavaRanch Style Guide. |