# problem on calculating Big O complexity

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();) {
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. Jun 19, 2014 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, 2014 at 13:12
• essentialy,in the worst case i must consider also the possible collisions?
– OiRc
Jun 19, 2014 at 13:22
• Correct. That is why you use BigOh notation. You are describing the worst case scenario when your algorithm runs. Jun 19, 2014 at 13:23
• @GeorgiAngelov in your opinion,is there a way to change this algorithm to avoid collisions?
– OiRc
Jun 19, 2014 at 13:25

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, 2014 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, 2014 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) Jun 19, 2014 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) Jun 19, 2014 at 13:57