Calculating Time Complexity of recursive function with iteration

Question

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?

Shailesh Suryawanshi · Accepted Answer · 2021-07-29 07:12:06Z

Consider this for generating the IP adresses from above algorithm we have two constraints.

Valid IP is from 0->255. This can be evaluated in constant time.
There will be 4 octets. So the question string should be divided into 4 parts.

Now consider a string 111 111 111 111 of length 12

How many way can you form the first octet? => minimum 1 , maximum 3 ways out of 12 characters. complexity:- O(3)
How many way can you form the second octet? => minimum 0 maximum 3 ways out of 9 character, considering 3 characters are used by first octet. complexity:- O(3)
How many way can you form the third octet? => minimum 0 maximum 3 ways from 6 character, considering 6 characters are used by first and second octet. complexity:- O(3)
How many way can you form the fourth octet with the remaining characters? => There is only one way to form an octet from the remaining 3 characters. considering 9 characters are used by the first, second, and third octet. O(1)

Time complexity Calculation.

Time Complexity = product of complexities of each recursive function
                = O(3)*O(3)*O(3)*O(1)
                = 3*O(3) = O(1) = [constant-time] complexity

So no matter what string you will give as an input all the valid IP addresses can be counted in 27 iterations. Therefore this algorithm is a constant time O(1).

Considering the above understanding the code can be re-written following way


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

        List<String> result = new ArrayList<>();
        // O(1) time complexity
        if (parts == 1) {
            if (position < s.length() && isValidPart(s.substring(position))) {
                result.add(s.substring(position));
            }
            return result;
        }

        // Iterate only thrice in each recursive function. O(3) time complexity
        for (int i = position; i <= position + 3; i++) {
            if (i > s.length()) {
                continue;
            }

            String first = s.substring(position, i);
            if (!isValidPart(first)) {
                continue;
            }

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

            for (String str : previous) {
                StringBuilder sb = new StringBuilder();
                result.add(first + "." + str);
            }
        }

        return result;

    }

Note that the above algorithm is one examples of classic backtracking problems. From wiki.

Backtracking is a general algorithm for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution

PS:- The example 111 111 111 111 is an extreme example and there is only one valid IP 111.111.111.111 address that can be formed from this string. However, the loop/recursion evaluation will happen a maximum of 81 times.

So the code I have written above isn't exactly backtracking unless I use the position parameter?
The code that you have written is the same as mine, the isValidPart checks for length 3, though your code doesn't iterate beyond 3 so lesser checks. But the one I have is still backtracking, right? based on the definition?
Both the codes, yours and mine are the same. I have optimized it so it will not iterate beyond 3. As you see any substring with a length of more than 3 is not a valid IP address. For length beyond 3, the isValidPart will always return false.
Yes, The code you and I have written is essentially backtracking. If you see we take a decision, decide if that leads to a solution, If it does not we backtrack. Which is to go one step back in the recursion tree here.
Thanks! Can you add some info wrt the runtime if this was a more generic problem. Basically is my runtime assessment correct where I use the factorial in a generic case?

Collectives™ on Stack Overflow

Calculating Time Complexity of recursive function with iteration

1 Answer 1

7 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Related