What is the time complexity of below recursive functions

Question

Below program is to find all the subsets of an array. Is time complexity of the program is O(2^n)?

Is there any easy way to find the time complexity of recursive function?

Thanks in anticipation

public static void getAllSubSet(int[] arr,int[] subset,int index){

        if(index == arr.length)
            printarr(subset);
        else{
            subset[index] = -1;
            getAllSubSet(arr, subset, index+1);
            subset[index] = arr[index];
            getAllSubSet(arr, subset, index+1);
        }

    }

    public static void printarr(int[] set){
        for(int i=0;i<set.length;i++){
            if(set[i] != -1){
                System.out.print(set[i] +" ");
            }
        }
        System.out.println("");

    }


    public static void main(String[] args) {
        // TODO Auto-generated method stub

        int[] arr = {1,2,3};
        int[] subset = new int[arr.length];

        getAllSubSet(arr, subset, 0);


    }

It is not in O(2^n). It is impossible to do better than Θ(n2^n) because that is the size of the output. — Paul
– Paul, Commented Jun 11, 2018 at 0:38
@Paulpro Yeah... my bad I forgot the print method... My main concern is about the recursive function. How to find the time complexity of recursive functions which are not dividing (like n-1 or n-2 in each recursive function) I know when function is dividing like n/2 or 3n/4 using masters method — Rohith Uppala
– Rohith Uppala, Commented Jun 11, 2018 at 0:39

Deepak Tatyaji Ahire · Accepted Answer · 2018-06-11 08:56:18Z

1

Answer to your first question:

The complexity of your function is O(n* 2^n). However if n is very large, you can neglect n.

Answer to your second question:

One of the best ways I find for approximating the complexity of the recursive algorithm is drawing the recursion tree. Once you have the recursive tree, you can find the complexity.

answered Jun 11, 2018 at 8:56

Deepak Tatyaji Ahire

5,3915 gold badges21 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

What is the time complexity of below recursive functions

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related