What could we the complexity proof of it?

Question

In an online assessment I got one coding challenge and I wrote one recursive code for it. The question was -

Given an integer n, return all the reversible numbers that are of length n.
A reversible number is a number that looks the same when rotated 180 degrees (looked at upside down).

 

Example:
Input: n = 2
Output: ["11","69","88","96"]

I wrote some kind of recursive approach and it passed.

    vector recursion(int n, int m) {
        if (n == 0) {
            vector res = {""};
            return res;
        }
        
        if (n == 1) {
            vector res = {"0", "1", "8"};
            return res;
        }
        
        vector ans = recursion(n - 2, m);
        vector res;
        
        for (auto subAns: ans) {
            // We can only append 0's if it is not first digit.
            if (n != m) {
                res.push_back('0' + subAns + '0');
            }
            
            res.push_back('1' + subAns + '1');
            res.push_back('6' + subAns + '9');
            res.push_back('8' + subAns + '8');
            res.push_back('9' + subAns + '6');
        }
        
        return res;
    }
    
    vector getAllNumbers(int n) {
        return recursion(n, n);
        
    }

I thought because we are calling 5 recursion it is something like 5^N but I want to do exact space and time complexity analysis for it.

Can anyone help me out what could be the exact solution, it is very tricky for me to figure out the exact space time complextiy for recursive approaches

user_2144669 · Answer

Observe first that there are Θ(5^n/2) valid numbers of length n. Given the recurrence

C(−2) = 0
C(−1) = 0
C(0) = 1
C(1) = 3
∀n ≥ 2, C(n) = 5 N(n−2),

there are C(n) − C(n−2) numbers. If n = 2k where k is an integer, then C(n) = 5^k. If n = 2k + 1, then C(n) = 3 (5^k).

The running time is Θ(5^n/2 n). We can write a recurrence

T(0) = O(1)
T(1) = O(1)
∀n ≥ 2, T(n) = T(n−2) + Θ(5^n/2 n),

where the latter term counts the cost of constructing Θ(5^n/2) numbers each of length n. This is not a terribly interesting recurrence; we end up with a sum whose terms decrease faster than geometrically, so it's Θ of its largest term.

Space usage will be asymptotically the same since space usage is bounded above by time and below by the total size of the output, which are the same Θ.

What could we the complexity proof of it?

1 Answers