What is the time complexity of below function?

user_13700070 0
Viewed 61

I was reading book about competitive programming and was encountered to problem where we have to count all possible paths in the n*n matrix. Now the conditions are : `

1. All cells must be visited for once (cells must not be unvisited or visited more than once)
2. Path should start from (1,1) and end at (n,n)
3. Possible moves are right, left, up, down from current cell
4. You cannot go out of the grid

Now this my code for the problem :

typedef long long ll;
ll path_count(ll n,vector<vector<bool>>& done,ll r,ll c){
    ll count=0;
    done[r][c] = true;
    if(r==(n-1) && c==(n-1)){
        for(ll i=0;i<n;i++){
            for(ll j=0;j<n;j++) if(!done[i][j]) {
                done[r][c]=false;
                return 0;
            }
        }
        count++;
    }
    else {
        if((r+1)<n && !done[r+1][c]) count+=path_count(n,done,r+1,c);
        if((r-1)>=0 && !done[r-1][c]) count+=path_count(n,done,r-1,c);
        if((c+1)<n && !done[r][c+1]) count+=path_count(n,done,r,c+1);
        if((c-1)>=0 && !done[r][c-1]) count+=path_count(n,done,r,c-1);
    }
    done[r][c] = false;
    return count;
}

Here if we define recurrence relation then it can be like: T(n) = 4T(n-1)+n2 Is this recurrence relation true? I don't think so because if we use masters theorem then it would give us result as O(4n*n2) and I don't think it can be of this order.

The reason, why I am telling, is this because when I use it for 7*7 matrix it takes around 110.09 seconds and I don't think for n=7 O(4n*n2) should take that much time.

If we calculate it for n=7 the approx instructions can be 47*77 = 802816 ~ 106. For such amount of instruction it should not take that much time. So here I conclude that my recurrene relation is false.

This code generates output as 111712 for 7 and it is same as the book's output. So code is right.

So what is the correct time complexity??

recurrence time-complexity
1 Answers

No, the complexity is not O(4^n * n^2).

Consider the 4^n in your notation. This means, going to a depth of at most n - or 7 in your case, and having 4 choices at each level. But this is not the case. In the 8th, level you still have multiple choices where to go next. In fact, you are branching until you find the path, which is of depth n^2.

So, a non tight bound will give us O(4^(n^2) * n^2). This bound however is far from being tight, as it assumes you have 4 valid choices from each of your recursive calls. This is not the case.

I am not sure how much tighter it can be, but a first attempt will drop it to O(3^(n^2) * n^2), since you cannot go from the node you came from. This bound is still far from optimal.

user_5726700
Related