How to calculate complexity of this program? Can there be any other solution with less complexity?

Question

Question link: https://leetcode.com/contest/biweekly-contest-1/problems/campus-bikes-ii/

I want to calculate the complexity of this program, I think the complexity of my code is O(b^w) where b is the size of total bikes and w is the size of total workers, though I'm not sure.

In my "bikeAssign()" function which basically works as dfs, At first 1st worker has b (total bikes) options to choose, 2nd has b-1 options to choose, so I think time complexity would be like this-

(b)(b-1)(b-2)......(b-w) which is nearly equals to O(b^w).

Space complexity: O(w) for dfs (bikeAssign()) only

public:
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        int w = workers.size();
        int b = bikes.size();
        vector<vector<int> > dist;

        //complexity O(w*b)
        for( vector<int> worker : workers ) {
            vector<int> v;
            for( vector<int> bike : bikes ) {
                v.push_back( abs(worker[0]-bike[0]) + abs(worker[1]-bike[1]) );
            }
            dist.push_back(v);
        }

        vector<int> vis(b,0);
        //complexity O(b^w) My calculation
        return bikeAssign(dist, vis, 0, w );
    }


    // COMPLEXITY OF THIS FUNCTION ????

    int bikeAssign( vector<vector<int> > &dist, vector<int> &vis, int cnt, int w ) {
        if( cnt == w )
            return 0;

        int res = INT_MAX;
        for( int i=0;i<dist[0].size();i++ ) {
            if( vis[i] == 0 ) {
                vis[i] = 1;
                res = min( res, dist[cnt][i] + bikeAssign( dist, vis, cnt+1, w) );
                vis[i] = 0;
            }
        }

        return res;
    }
};

This solution is accepted, but I'm getting confused in complexity. Can someone help me to figure out- 1. The complexity of this program with an explanation. 2. Let me know if there is any other solution with a better complexity.

Any help would be appreciated.

Answer 1

Since this algorithm recursively scans all possible variation without repetition of bikes collected by workers, complexity is proportional to this number of variations.

So it is o(b!/(b-w)!) where b = bikes.size() and w = workers.size(). So this algorithm doesn't scale very well.

This looks like a problem similar to traveling salesman problem (but you have multiple "salesmans").