How do I find the complexity of this recursive algorithm? Replace pattern in string with binary number

Question

This algorithm essentially finds the star (*) inside a given binary string, and replaces it with 0 and also 1 to output all the different combinations of the binary string.

I originally thought this algorithm is O(2^n), however, it seems to me that that only takes into account the number of stars (*) inside the string. What about the length of the string? Since if there are no stars in the given string, it should technically still be linear, because the amount of recursive calls depends on string length, but my original O(2^n) does not seem to take that into account as it would become O(1) if n = 0.

How should I go about finding out its time and space complexity? Thanks.

Code:

static void RevealStr(StringBuilder str, int i) {
    //base case: prints each possibility when reached
    if(str.length() == i) {
        System.out.println(str);
        return;
    }
    //recursive step if wild card (*) found
    if(str.charAt(i) == '*') {
        //exploring permutations for 0 and 1 in the stack frame
        for(char ch = '0'; ch <= '1'; ch++) {
            //making the change to our string
            str.setCharAt(i, ch);
            //recur to reach permutations
            RevealStr(str, i+1);
            //undo changes to backtrack
            str.setCharAt(i, '*');
        }
        return;
    }
    else
        //if no wild card found, recur next char
        RevealStr(str, i+1);
}

Edit: I am currently thinking of something like, O(2^s + l) where s is the number of stars and l the length of the string.

Answer 1

The idea of Big-O notation is to give an estimate of an upperbound, i.e. if the order of an algorithm is O(N^4) runtime it simply means that algorithm can't do any worse than that.

Lets say, there maybe an algorithm of order O(N) runtime but we can still say it is O(N^2). Since O(N) never does any worse than O(N^2). But then in computational sense we want the estimate to be as close and tight as it will give us a better idea of how well an algorithm actually performs.

In your current example, both O(2^N) and O(2^L), N is length of string and L is number of *, are valid upperbounds. But since O(2^L) gives a better idea about algorithm and its dependence on the presence of * characters, O(2^L) is better and tighter estimate (as L<=N) of the algorithm.

Update: The space complexity is implementation dependant. In your current implementation, assuming StringBuilder is passed by reference and there are no copies of strings made in each recursive call, the space complexity is indeed O(N), i.e. the size of recursive call stack. If it is passed by value and it is copied to stack every time before making call, the overall complexity would then be O(N * N), i.e. (O(max_number_of_recursive_calls * size_of_string)), since copy operation cost is O(size_of_string).