Question

Suppose you have some List of S List of Strings called List and a String prefix. Write a method that removes all the Strings from list that begin with prefix. public void removePrefixStrings(List-String- list, String prefix) 7. What is the time complexity of this algorithm?

Answer 1

public void removePrefixStrings(List<String> list , String prefix) {

if(list==null || list.size()==0)

return;

for(int i=0; i<list.size();) {

if(list.get(i).startsWith(prefix))

list.remove(i);

else

++i;

}

}

Time Complexity: If the prefix is the same as String length, Then finding all prefix match will take n *n = n2

Then removal is also n

So the total time complexity is O(n3)