CODEWITHSUNDEEP
javaalgorithmforeachtime-complexity
Leonardo Vinsen
Leonardo Vinsen

Reputation: 89

Is the time complexity of this algorithm O(N^2)?

Currently I'm learning about algorithm efficiency in terms of time and space complexity.
I have this algorithm written in Java: 

String[] remove = value.split(",");
String[] temp = (pb.get(key)).split(",");
String newval = "";

for (int i=0;i<remove.length;i++){
    for (int j=0;j<temp.length;j++){
        if (remove[i].equals(temp[j])){
           temp[j] = "";
        }
    }
}
for (String str : temp){
    if (!(str.isEmpty())){
        newval = newval + "," + str;
    }
}
newval = newval.substring(1, newval.length());
pb.put(key, newval);

From my understanding, the first loop (nested loop) would have a time complexity of O(N^2) and the second loop would be O(N). Am I correct?
And how do I calculate for the space complexity ?

Also, an unrelated question; how do I change the first loop into an enhanced for-loop ?

Thanks in advance!

Upvotes: 1

Views: 157

Answers (2)

FallAndLearn
FallAndLearn

Reputation: 4135

Time complexity : O(N^2) : You yourself told the answer. Also, substring() method is a linear time operation in Java 7.

Space complexity : O(m+n) : As you are using two arrays having size lets say m and n.

To your other question, enhanced for loop can be used like below

for(String str1 : remove){
 for(String str2 : temp){
   if(str1.equals(str2)){
     //
   }
 }
}

Upvotes: 1

Xavier Silva
Xavier Silva

Reputation: 267

Yes, the time complexity is O(N^2) because of what you said: first loop's time complexity is O(N^2) and the second one is O(N) (you choose the worst (bigger) one). You have, still, to pay attention to all the methods you invoke like subtring(...) because one of them can have a bigger time complexity, what will change the overall time complexity.

Hope this helps you.

Upvotes: 1

Related Questions