4 replies to this topic

[Koeneuze]

Right, i'm new here, so i hope people don't mind me starting out with already asking for help, but i'm in a bit of a hurry. (I'm pretty new at Java, though i'm experienced in php, html, css, javascript, mysql, so no need to worry about basics ;) )

My programming exam (Bachelor Mathematics, we get one semester of programming) is coming up, and i managed to get my hands on the exam of two years ago. One of the questions is troubling me:

You get this code:

public static void Simuleer1()

{

String bs = "Hello world!";

int max = -1;

char let = '*';

int counter = 0;

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 + " times " + let);

}

(Any possible mistakes in there are due to mistranslations on my part)

So, practically we have a code telling us which character is found most in a String. If two chars are found equally often, the one that first appears gets shown.

Questions are:
1) What will the output be for the given string?
Well, that's a piece of cake, of course.

2) What is the time complexity (not sure if i translated this correctly) of this code?
Since we're using a for-loop in a for-loop, i personally think it's quadratic / O(n²); although that since the innermost loop keeps getting shorter, it may be linear*logarithmic / O(n log n) ?

3) Can we reduce the time complexity of this code, and if so, how?
Well, since there's no "and if not, ..." in the question, i'll assume the answer is yes. I've though about a few ways to shorten the second loop, but nothing to get to a linear / O(n) or logarithmic / O(log n) time complexity.


Any help is appreciated!

Thanks in advance! :D

[WingedPanther]

It's O(n^2).

I think the best you'll be able to get it to is O(n ln(n)), because you'll have to store the counts in a structure (probably a hash list), which will probably have access O(n ln(n)) as an inherent property.

[Koeneuze]

Thanks for the reply!

I'm still thinking of a good way to reduce time complexity. Although i can work with HashLists, like you suggested, i think we're supposed to use either a Set, a HashMap or an ArrayList.

God, i hate having to make a wrapper class for putting a char into an arraylist. If anyone has a different idea on how to reduce time complexity, please, do tell! :)

[wim DC]

For java's primitive types (that don't go in a collection) there allready are wrapper classes, they start with a capital letter and have the full word as name:

int -> Integer

char -> Character

double -> Double

If you go for the least for-loops, you can do it in 1 for-loop, using a Map.

    String word = "Hi i speak dutch.";

    Map<Character, Integer> letterCount = new HashMap<Character, Integer>();

    char maxLetter = word.charAt(0);


    for( int i=0 ; i<word.length() ; i++){

      char letter = word.charAt(i); 

      if( !letterCount.containsKey(letter) ){

        letterCount.put(letter, 0);

      }

      int count = letterCount.get(letter)+1;

      letterCount.put( letter, count);

    

      if(letterCount.get(maxLetter) < count ) {

        maxLetter = letter;

      }

    }


    System.out.println("'" + maxLetter + "' - " + letterCount.get(maxLetter) + " times.");

(Code also counts spaces)

[Koeneuze]

Thanks, this works perfectly! So, since we're only using one loop, i assume this is O(n), or does the fact we need to use get methods on the hashmap make it O(n log n) ?