Reducing time complexity using HashMap, or is there a better method?

Question

Right, this is from an older exam which i'm using to prepare my own exam in january. We are given the following method:

public static void Oorspronkelijk()
{
    String bs = "Dit is een boodschap aan de wereld";
    int max = -1;
    char let = '*';
    for (int i=0;i<bs.length();i++) {
        int tel = 1;
        for (int j=i+1;j<bs.length();j++) {
            if (bs.charAt(j) == bs.charAt(i)) tel++;
        }

        if (tel > max) {
            max = tel;
            let = bs.charAt(i);
        }
    }

    System.out.println(max + " keer " + let);
}

The questions are:

1. what is the output? - Since the code is just an algorithm to determine the most occuring character, the output is "6 keer " (6 times space)
2. What is the time complexity of this code? Fairly sure it's O(n²), unless someone thinks otherwise?
3. Can you reduce the time complexity, and if so, how?

Well, you can. I've received some help already and managed to get the following code:

public static void Nieuw()
{
    String bs = "Dit is een boodschap aan de wereld";
    HashMap<Character, Integer> letters = new HashMap<Character, Integer>();
    char max = bs.charAt(0);
    for (int i=0;i<bs.length();i++) {
        char let = bs.charAt(i);
        if(!letters.containsKey(let)) {
            letters.put(let,0);
        }

        int tel = letters.get(let)+1;
        letters.put(let,tel);

        if(letters.get(max)<tel) {
            max = let;
        }
    }

    System.out.println(letters.get(max) + " keer " + max);
}

However, I'm uncertain of the time complexity of this new code: Is it O(n) because you only use one for-loop, or does the fact we require the use of the HashMap's get methods make it O(n log n) ?

And if someone knows an even better way of reducing the time complexity, please do tell! :)

Answer 1

The time complexity of the new code is O(n) - this is because the hashmap lookup is a constant time operation and constant time operation do not affect the order.

One suggestion I could make, just an optimisation though (won't make a huge difference) - not a major change and won't affect the order - is that you could use an array of ints rather than a hash map to track counts of each character. Just use the int value equivalent of the char as the index of the array.

Answer 2

a hash function get operation is O(1), so your solution's time complexity is O(n). you can't do better than that since any solution would require you to read the entire input at least once.

Answer 3

I think it is O(n) . because searching in HashMap is just O(1)

for (int i=0;i<bs.length();i++) { // O(n)
    char let = bs.charAt(i); // O(1)
    if(!letters.containsKey(let)) { // O(1)
        letters.put(let,0);
    }

the overall complexity is O(n)

Answer 4

To ensure, the HashMap will always have the time complexity of O(1), you may have to enter proper initialCapacity. You need to know the complete domain values that the bs String is going to have.

Assuming, 1. Both Upper and Lower cases will be treated seperately. 2. The string will only have alphabets and a space charecter

The inital Load capacity should be greater than, 26(lower case) + 26 (Upper case) + 1(Space) = 53

53 + 25%(53) = 53 + 13.25 + 2.75(buffer) = 69.

So the hashmap initiation could be like the below,

HashMap<Character, Integer> letters = new HashMap<Character, Integer>(69);

Answer 5

Hashmap is O(1), but here you can also use an array, since the number of letters is fairly small (only 256) you can also use an Array. This is also O(1), but is faster, uses less memory, and it's simpler:

String bs = "Dit is een boodschap aan de wereld";
int letters[] = new int[256];
char max = 0;
for (int i=0;i<bs.length();i++) {
    char let = bs.charAt(i);
    ++letters[let];

    if(letters[max] < letters[let]) {
        max = let;
    }
}

System.out.println(letters[max] + " keer " + max);