1

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!

Leonardo Vinsen
  • 89
  • 1
  • 12
  • 2
    Yup thats right and space complexity is m+n assuming size of arrays is m & n respectively – Sanjeev May 17 '16 at 11:25
  • Possible duplicate of [How to find time complexity of an algorithm](http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – Bilesh Ganguly May 17 '16 at 11:31

2 Answers2

1

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.

Xavier Silva
  • 267
  • 1
  • 19
1

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)){
     //
   }
 }
}
FallAndLearn
  • 4,035
  • 1
  • 18
  • 24
  • how do I replace temp[j] in my for-loop so it would fit in the algorithm, since there is no pointer variable (which was int j) ? – Leonardo Vinsen May 17 '16 at 15:26
  • Use it according to your requirement. If you want to use indexes. Then don't use enhanced for loop in the inner loop. – FallAndLearn May 17 '16 at 16:25
  • thanks for the answers! I just thought that it would look weird if I combine enhanced for loop and the normal for loop. Any thoughts on that ? – Leonardo Vinsen May 17 '16 at 17:44