Java Program using Big O(n log n) or Big O(log n) complexity

user_15044990 0
Viewed 166

I am trying to create a Java program to find the common elements/ages between 2 arrays. However, I need the algorithm has to run on Big O(n log n) or Big O(log n) time complexity. This is what I came up with, any ideas on how to improve it? Am I counting of the steps of the operation correctly as well?

int [] AgeMale = {21, 19, 24, 22, 20, 23, 18};  //Program is executed 1 time
int [] AgeFemale = {17, 17, 22, 19};            //Program is executed 1 time
System.out.println("Age of male students: " + Arrays.toString(AgeMale)); //Title. Program is executed 1 time
System.out.println("Age of female students: " + Arrays.toString(AgeFemale)); //Title. Program is executed 1 time
    
for (int x = 0; x < AgeMale.length; x++) //Loop is executed n times, therefore, O(n).
{
    for (int y = 0; y < AgeFemale.length; y++) //Loop is executed n times, therefore O(n).
    {
        if (AgeMale[x] == AgeFemale[y])     // Executed n * n time 
        {
                System.out.println("The common ages are: " + AgeMale[x]); // Program is executed 1 time.
        }
    }
}
big-o time-complexity java performance
1 Answers

Your current algorithm has a complexity of O(mn), with m being the number of elements in the array AgeMale and n begin the number of elements in the array AgeFemale.

To improve your algorithm, you can convert one of the arrays into a set (e.g., an HashSet). From source one can read:

Time Complexity of HashSet Operations: The underlying data structure for HashSet is hashtable. So amortize (average or usual case) time complexity for add, remove and look-up (contains method) operation of HashSet takes O(1) time.

You can choose the smallest of the two arrays to be converted into set. The conversion from an array into a set will have a time complexity of S, where S is the size of the smallest array. In other words, the method add from the HashSet will be called S times.

Then just check if the elements of the largest array are present on that set. This will have a time complexity of L, where L is the size of largest array.

Overall the aforementioned algorithm has a time complexity of O(S + L).

A running example:

public static void main(String[] args) {
    int [] ageMale = {21, 19, 24, 22, 20, 23, 18};  //Program is executed 1 time
    int [] ageFemale = {17, 17, 22, 19};            //Program is executed 1 time
    System.out.println("Age of male students: " + Arrays.toString(ageMale));
    System.out.println("Age of female students: " + Arrays.toString(ageFemale));
    Set<Integer> female_ages = new HashSet<>(ageFemale.length);
    for (int age : ageFemale) // Time complexity of O(S)
        female_ages.add(age); // Time complexity of O(1)

    for (int age : ageMale) { // Time complexity of O(L)
        if(!female_ages.add(age)){ // Time complexity of O(1)
            System.out.println("The common ages are: " + age);
        }
    }
}

Output:

Age of male students: [21, 19, 24, 22, 20, 23, 18]
Age of female students: [17, 17, 22, 19]
The common ages are: 19
The common ages are: 22
user_13668710
Related