# What's the time complexity for my recursive solution ??

• I had hard time to analyze the time complexity for my solution, so anyone can help analyze what is the time complexity for non-DP and DP solutions (below is with DP support, can be easily modified to remove DP support) ??

``````public class Solution {
Map<String,List<Integer>> map = new HashMap<>();
public List<Integer> diffWaysToCompute(String input) {
List<Integer> res = new ArrayList<>();
if(input.isEmpty())
return res;
if(map.containsKey(input))
return map.get(input);
boolean isPureNum = true;
for(int i=0; i<input.length(); i++) {
if(input.charAt(i)=='+' || input.charAt(i)=='-' || input.charAt(i)=='*') {
isPureNum = false;
List<Integer> prefixes = diffWaysToCompute(input.substring(0,i));
for(int prefix : prefixes) {
List<Integer> postfixes = diffWaysToCompute(input.substring(i+1));
for(int postfix : postfixes) {
if(input.charAt(i)=='+')
else if(input.charAt(i)=='-')
else
}
}
}
}
if(isPureNum) {
map.put(input, res);
return res;
} else {
map.put(input, res);
return res;
}
}
}``````

• without cache time complexity should be O(n!) and n is the number of operators.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.