0

i have this function on which i have to calculate the time complexity with the Big O notation:

public void print(ArrayList<String> operations, ArrayList<LinkedHashSet<String>> setOfStrings) {
    int numberOfStrings = 0;
    int numberOfLetters = 0;
    String toPrint = operations.get(1);
    for (Iterator<LinkedHashSet<String>> iteratorSets = setOfStrings.iterator(); iteratorSets.hasNext();) {
        LinkedHashSet<String> subSet = iteratorSets.next();
        if (subSet.contains(toPrint)) {
        for (Iterator<String> iterator = subSet.iterator(); iterator.hasNext();) {
            numberOfLetters = numberOfLetters + iterator.next().length();
        }
        numberOfStrings = subSet.size();
        break;
        }
    }
}

the method does this operation:

For example, if have as operation print foo, I have to do these steps,first of all, I have to find where foo is:

  • Inside setOfStrings, I can have this situation:

            position 1 : [car, tree, hotel]
            ...
            position n : [lemon, coffee, tea, potato, foo]
    
  • When I find the string foo, I have to save the number of strings inside that position and the number of letters of each string, so in this case, I will save:

       5(number of strings) 23(sum of number of letters)
    

some considerations:

  1. For the arrayList of operations, I get always a specific position, so I don't iterate. It is always O(1).

  2. For the ArrayList<LinkedHashSet<String>> , I have to iterate, so the complexity in the worst case is O(n)

  3. the operation if (subSet.contains(toPrint)), it will be O(1),because hashSet has mapped all objects inside it.

  4. the iteration inside the hashset made with for (Iterator<LinkedHashSet<String>> iteratorSets = setOfStrings.iterator(); iteratorSets.hasNext();) , it will be O(m),because i have to iterate inside the entire hashset to sum the letters of each words

so in conclusion i think the time complexity of this algorithm is(O(n)*O(m))

are these considerations all corrects? thanks.

  • Essentially, yes. If the situation is as you have described it, then you complexity is O(nm). Like you saud, given than you have nested loops with each one possibly having n and m number of objects, respectively, then the complexity of O(nm) follows. – Georgi Angelov Jun 19 '14 at 13:09
  • ok,but if in the specific hashset , on which i have to search the word there are collisions,i think the complexity would be O(n*m^2) or not? – OiRc Jun 19 '14 at 13:12
  • essentialy,in the worst case i must consider also the possible collisions? – OiRc Jun 19 '14 at 13:22
  • Correct. That is why you use BigOh notation. You are describing the worst case scenario when your algorithm runs. – Georgi Angelov Jun 19 '14 at 13:23
  • @GeorgiAngelov in your opinion,is there a way to change this algorithm to avoid collisions? – OiRc Jun 19 '14 at 13:25
1

It is a bit more complicated than that. The worst-case complexity is O(M * N), and the best-case complexity is O(N).

There are two worst-case scenarios:

  • when every subset contains the toPrint String, or
  • when the subsets contain strings that all has to the same value.

(The second one is extremely unlikely, unless someone deliberately populates the data structure with data with that property. But it is still a case that needs to be considered in a thorough complexity analysis.)

The best-case scenario is when strings in the subsets hash "nicely" AND the probability of the contains test returning true tends to zero.

Finally, N is the size of setOfStrings, and M is the average size of a subset.

  • the first scenario never happens,i'm sure about that,i don't understand the second scenario that you mentioned, so as @GeorgiAngelov says,for this algorithm ,i have to consider also the probability of collision,so the complexity will be O(m*n^2) or not? – OiRc Jun 19 '14 at 13:32
  • so it is not true that contains of set is O(1),for the collisions in first and in secondly if the word is in the last position of the hash set. – OiRc Jun 19 '14 at 13:35
  • It would not be O(1) since search time can take O(M), in case of collision and in case of toPrint being the last link in the chain. That should not affect the complexity however, since it becomes O(nM*2) as opposed to O(nM^2) – Georgi Angelov Jun 19 '14 at 13:36
  • The worst case scenario is O(nm) because you iterate n times at worst. In one iteration, you check for contains() which can be O(m) at worst. So it is now O(mn), after that you count the number of letters which is just O(m) and break. so O(mn) + O(m) is O(mn) – InformedA Jun 19 '14 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.