#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) {
        if (isValidPart(s)) result.add(s);
        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();
            result.add(first + "." + str);
        }
    }        
    
    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!!!

Leave a Reply

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