Skip to main content
edited tags
Link
user40980
user40980
Source Link
OiRc
  • 127
  • 1
  • 1
  • 9

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();) {
        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.