i was trying to solve job assignment problem i started to solve job assingment problem using naive approach using recursion and got
TLE on geeksforgeeks
to optimise my code i used recursion with memoization and submitted my code and got TLE again(shocked) but i am not able to identify time complexity of my code... plz anyOne Help me to find out complexity of my below code and why it is not working and giving TLE
asked 22 Feb '18, 12:43

Your recurrence relation is: T(n)=(n1)*T(n1) + O(n)
answered 22 Feb '18, 13:36
And yeah there will be no use of memoization here since there are n! States in ur recurrence.
(22 Feb '18, 16:29)
@vivek_1998299 since time complexity for 0/1 knapsack recursion was 2^n.. still when we used memoization we are able to reduced it to n^2.. so how to find time complexity of job assignment problem using recursion with memotization(above my code is written) , so that i can optimise my code further .. thanks in advance
(22 Feb '18, 20:34)
1
It is not necessary that memoization will always reduce the complexity.In knapsack the max number of state was n^2,hence it was useful to memoize(as we didnt need to calculate same thing again and again),however in ur case max number of state is 2^n,thats why i said no use of memoisation.
(22 Feb '18, 20:45)
Memoisation just helps in avoiding recalculation of state.
(22 Feb '18, 20:49)
thanks bro.. i also came up to conclusion that minimum i have to calculate minimum for 2^n states AS nC1 + nC2 + nC3+ ...... nCn = 2^n 1 states
(22 Feb '18, 21:02)
Sorry i mean n! States
(22 Feb '18, 21:05)
showing 5 of 6
show all
