Why is sorting/initializing an array not counted in Big O?

Question

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:

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

Loop O(n) + sort (n lg(n)) = O(n lg(n)) .

user1935024
– user1935024

2014-08-24 15:07:35 +00:00
Commented Aug 24, 2014 at 15:07 — user1935024
– user1935024, Commented Aug 24, 2014 at 15:07

pascalh · Accepted Answer · 2014-08-24 15:07:22Z

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)

answered Aug 24, 2014 at 15:07

pascalh

5,8764 gold badges34 silver badges46 bronze badges

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

1 Comment

user1390463 Over a year ago

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.

TheLostMind · Accepted Answer · 2014-08-24 15:15:10Z

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)

edited Aug 24, 2014 at 15:15

answered Aug 24, 2014 at 15:09

TheLostMind

36.3k12 gold badges72 silver badges109 bronze badges

1 Comment

user1390463 Over a year ago

Thank you TheLostMind. Silly mistake on my part.

Collectives™ on Stack Overflow

Why is sorting/initializing an array not counted in Big O?

2 Answers 2

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related