Reducing Time Complexity in Java
- by Koeneuze
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:
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)
What is the time complexity of this code?
Fairly sure it's O(n²), unless someone thinks otherwise?
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! :)
