Time Complexity Analysis of Recursive Approach


  • 0
    M

    On the first thought, the time complexity analysis of this brute force approach looks difficult. We are going through each elements and calling recursively on each of those elements. Is it n ^ n ?

    The fact that we are doing brute force gives us the answer of complexity. If you think, we are essentially selecting all possible subsets of of set.

    {1,2,3} -> {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3}

    There are 2 ^n such elements and hence the time complexity is O(2^n)

    Example:
    It is easy to see this with example also. We select input that will explore all the paths such as {1,2,3,4,5,6,7} and the target is big enough so it will not prune any path. It will call the iteration 128 times.

    public class Solution {
    	  public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    	        
    	        List<List<Integer>> answer = new ArrayList<>();
    	        if(candidates == null || candidates.length == 0){return answer;}
    	        
    	        // Sort the array, it is needed to take care of duplicates and effective pruning
    	        Arrays.sort(candidates);
    	        
    	        dfs(0, candidates, target, new ArrayList<>(), answer);
    	        return answer;
    	    }
    	    
    	   private static int complexity = 0; 
    	  
    	    private void dfs(int index, int candidates[], int target, List <Integer> path, List<List<Integer>> answer){
    	        if(target == 0){
    	            // The path gives us answer
    	            answer.add(new ArrayList<>(path));
    	            // Return back as numbers after this will be bigger and will not give us answer
    	            return;
    	        }
    	        
    	        complexity ++;
    	        
    	        for(int i = index; i < candidates.length; i++){
    	            
    	            // Avoid visiting duplicate elements
    	            if(i != index && candidates[i] == candidates[i-1]){ continue; }
    	            
    	            // This element and all that will appear after this are too big
    	            if(target - candidates[i] < 0){break;}
    	                
    	            path.add(candidates[i]);
    	            
    	            dfs(i + 1, candidates, target-candidates[i], path, answer);
    	            
    	            path.remove(path.size()-1);
    	        }
    	    }
        public static void main(String[] args) {
    		System.out.println(new Solution().combinationSum2(new int []{1,2,3,4,5,6,7}, 1000));
    		System.out.println(complexity);
    	}
    }
    

  • 0
    A

    Actually, I think for the time complexity it should be the sum of C(n, n) + C(n, n - 1) + C(n, n - 2) + C(n, n - 3) + .... + C(n, 1) ~= n^n


Log in to reply
 

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