0

I am trying to find the most efficient answer (without using a HashMap) to the problem: Find the most frequent integer in an array.

I got answers like: 

public int findPopular(int[] a) {

if (a == null || a.length == 0)
    return 0;

Arrays.sort(a);

int previous = a[0];
int popular = a[0];
int count = 1;
int maxCount = 1;

for (int i = 1; i < a.length; i++) {
    if (a[i] == previous)
        count++;
    else {
        if (count > maxCount) {
            popular = a[i-1];
            maxCount = count;
        }
        previous = a[i];
        count = 1;
    }
}

return count > maxCount ? a[a.length-1] : popular;

}

and 

public class Mode {
public static int mode(final int[] n) {
    int maxKey = 0;
    int maxCounts = 0;

    int[] counts = new int[n.length];

    for (int i=0; i < n.length; i++) {
        counts[n[i]]++;
        if (maxCounts < counts[n[i]]) {
            maxCounts = counts[n[i]];
            maxKey = n[i];
        }
    }
    return maxKey;
}

public static void main(String[] args) {
    int[] n = new int[] { 3,7,4,1,3,8,9,3,7,1 };
    System.out.println(mode(n));
}
}

The first code snippet claims to be O(n log n). However, the Arrays.sort() function alone is O(n log n) [3]. If you add the for loop, wouldn't the findPopular() function be O(n^2 * log n)? Which would simplify to O(n^2)?

The second code [2] snippet claims to be O(n). However, why do we not consider the initialization of the arrays into our calculation? The initialization of the array would take O(n) time [4], and the for loop would take O(n). So wouldn't the mode() function be O(n^2)?

If I am correct, that would mean I have yet to see an answer that is more efficient than O(n^2).

As always, thank you for the help!

Sources:

  1. Find the most popular element in int[] array

  2. Write a mode method in Java to find the most frequently occurring element in an array

  3. The Running Time For Arrays.Sort Method in Java

  4. Java: what's the big-O time of declaring an array of size n?

Edit: Well, I feel like an idiot. I'll leave this here in case someone made the same mistake I did.

Community
  • 1
  • 1
user1390463
  • 83
  • 8

2 Answers2

1

When you perform two tasks one after the other, you add complexities:

Arrays.sort(a); // O(n log n)
for (int i = 0; i < n; i++) { // O(n)
    System.out.println(a[i]);
}
// O(n log n + n) = O(n (log n + 1)) = O(n log n)

Only when you repeat an algorithm, you will multiply:

for (int i = 0; i < n; i++) { // O(n)
    Arrays.sort(a); // O(n log n), will be executed n times
}
// O((n log n) * n) = O(n² log n)
pascalhein
  • 5,700
  • 4
  • 31
  • 44
  • Thank you for walking through it. I have no idea what I was thinking when I multiplied the operations. I guess I saw what I wanted to see. – user1390463 Aug 24 '14 at 16:00
0

code -1 : you have only one for loop . So effectively, your time complexity will be : O(n Log n) + O(n) approximately equal to (n Log n)

code-2: Initialization also takes O(n). So effectively, O(n) + O(n) (loop) is still O(n).

Note : While calculating time-complexities with O (big-O), you just need the biggest term(s)

TheLostMind
  • 35,966
  • 12
  • 68
  • 104