# #StackBounty: #java #recursion #backtracking Calculating Time Complexity of recursive function with iteration

### Bounty: 50

I am trying to understand the time complexity for this code which calculates IP addresses given a string by splitting the string into 4 parts. Each part is separated by a period i.e. `.`

``````public List<String> restoreIpAddresses(String s, int parts) {

List<String> result = new ArrayList<>();
if (parts == 1) {
return result;
}

for (int i = 0; i < s.length(); i++) {
String first = s.substring(0, i);
if (!isValidPart(first)) {
continue;
}

List<String> previous = restoreIpAddresses(s.substring(i, s.length()), parts - 1);

for (String str: previous) {
StringBuilder sb = new StringBuilder();
}
}

return result;

}

private boolean isValidPart(String part) {
if ( (part.length() > 1 && part.startsWith("0")) ||
(part.length() > 3) || (part.length() == 0)
(Integer.valueOf(part) > 255) ) return false;
return true;
}
}
``````

Since the for loop is `O(n)`, n being the length of the string, and in each iteration the for loop executes for the substring that was passed in the parent for loop, so `O(n - 1)`. So by this logic, the time complexity should be `n(n-1)(n-2) ....1` i.e. `n!` in the worst case, right?

However if I look around (eg. here or here), I see people posting constant time complexity. I am unable to understand. Can someone help me break it down?

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.