# What is the Time complexity of following code?

Problem Statement:
There are 2*N Chess players and N Boards in a chess tournament. The rating of the Chess Player is given by array A . Every player can play only with one player. N board pairing is to be done, and if you match Player i and Player j in the board K, then the Happiness Score increases by K * abs(A[i] - A[j]) * gcd(A[i], A[j]). Find the Maximum Happiness score you can make by designing an ideal pairing. Every player should play a match.

Constraints:
1 <= N <= 10
1 <= A[i] <= 10^6

Here are two solutions

I think the time complexity of both the solutions are same the only difference between them being the memory optimization.

We can see a relation between board and mask that board = (count of bits in mask) / 2 + 1 (did +1 to convert number of board to 1 based indexing)

Now since for a given mask, board value is fixed, we can drop the board from our dp state.
But doing this will only lead to memory optimisation. Will that lead to any time complexity improvement?

The tutor who taught this problem told that the time complexity of Solution-1 will be O(N^3 * 2^N) while the complexity of Solution-2 will be O(N^2 * 2^N). But I think the time complexity of both the solution should be same as there are same number of recursive calls.

Please correct me if I am wrong.

The solution 1 has out of bounds accesses because it may access `dp[10][mask]` and the array is not large enough. The time complexity of the solution 1 is indeed N times worse because it needs N times more memory and also does N times more calculations to populate the larger DP array.

You can also benchmark these solutions yourself to see which of them is faster and how the time changes for different N. For example, a O(N^2) solution would take roughly 4 times longer to process a twice larger N. And a O(N^3) solution would take roughly 8 times longer to process a twice larger N. If you don’t observe the expected performance differences, then your time complexity estimation may be wrong.

Ohhh…I think I got this now…The first solution performs poor just because the memset will initialise the dp array that is N times larger than the dp array of the second solution…but the time complexity of the sole recursive function is still the same right because in both the cases the total number of calls would be the same, am I correct?. In the first solution, a lot of states are not going to visited. The overall complexity has an extra factor of N just because of the memset initialization, right? @ssvb