You are not logged in. Please login at www.codechef.com to post your questions!

×

# what will be time complexity if there are total N problems and each problem is divided into N-1 subproblems and what when i will use memoizatio with recursion on same problem? plz help..

 0 i was trying to solve job assignment problem geeksforgeeks problem link geeksforgeeks solution article i started to solve job assingment problem using naive approach using recursion and got TLE on geeksforgeeks as i came to know using permutation and combination concept complexity for my recursion approach is O(n!) but dont know how to calculate complexity using recursion tree or any other approach below is my Code for naive approach  public class AssignmentProblemUsingRecursionNoMemoization { static int jobs; static int taskCost[][]; public static void main(String[] args) { Scanner s = new Scanner(System.in); int T = s.nextInt(); for (int i = 0; i < T; i++) { jobs = s.nextInt(); //cost of each task by each machine.. rows==task , coulumn== machine taskCost = new int[jobs][jobs]; for (int j = 0; j < jobs; j++) { for (int k = 0; k < jobs; k++) { taskCost[j][k] = s.nextInt(); } } System.out.println(calculate(0, 0, new int[jobs])); } } public static int calculate(int taskNumberjoHogaab, int costTillNow, int arrJoTaskJoHogyeYaNhi_Btayega[]) { if (taskNumberjoHogaab == jobs) { return 0; } int min = 101; for (int k = 0; k < arrJoTaskJoHogyeYaNhi_Btayega.length; k++) { if (arrJoTaskJoHogyeYaNhi_Btayega[k] == 0) { int newArr[] = copyArr(arrJoTaskJoHogyeYaNhi_Btayega); newArr[k] = 1; min = Math.min(taskCost[taskNumberjoHogaab][k] + calculate(taskNumberjoHogaab + 1, costTillNow + taskCost[taskNumberjoHogaab][k], newArr), min); } } return min; } public static int[] copyArr(int arr[]) { int newArray[] = new int[arr.length]; for (int p = 0; p < arr.length; p++) { newArray[p] = arr[p]; } return newArray; } }  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  public class AssignmentProblemUsingRecursionMemoization { static int jobs; static int taskCost[][]; static HashMap map; public static void main(String[] args) { Scanner s = new Scanner(System.in); int T = s.nextInt(); for (int i = 0; i < T; i++) { jobs = s.nextInt(); //cost of each task by each machine.. rows==task , coulumn== machine taskCost = new int[jobs][jobs]; map = new HashMap(); for (int j = 0; j < jobs; j++) { for (int k = 0; k < jobs; k++) { taskCost[j][k] = s.nextInt(); } } System.out.println(calculate(0, 0, new int[jobs])); } } public static int calculate(int taskNumberjoHogaab, int costTillNow, int arrJoTaskJoHogyeYaNhi_Btayega[]) { if (taskNumberjoHogaab == jobs) { return 0; } String arrStr = arrayToString(arrJoTaskJoHogyeYaNhi_Btayega); if (map.get(arrStr) != null) { return map.get(arrStr); } int min = 0;//101; for (int k = 0; k < arrJoTaskJoHogyeYaNhi_Btayega.length; k++) { if (arrJoTaskJoHogyeYaNhi_Btayega[k] == 0) { int newArr[] = copyArr(arrJoTaskJoHogyeYaNhi_Btayega); newArr[k] = 1; int tempCost = taskCost[taskNumberjoHogaab][k] + calculate(taskNumberjoHogaab + 1, costTillNow + taskCost[taskNumberjoHogaab][k], newArr); if (min == 0) { min = tempCost; } else { min = Math.min(tempCost, min); } } } map.put(arrayToString(arrJoTaskJoHogyeYaNhi_Btayega), min); return min; } public static int[] copyArr(int arr[]) { int newArray[] = new int[arr.length]; for (int p = 0; p < arr.length; p++) { newArray[p] = arr[p]; } return newArray; } public static String arrayToString(int arr[]) { String str = ""; for (int k = 0; k < arr.length; k++) { str = str + arr[k]; } return str; } }  asked 22 Feb '18, 12:43 533●1●12 accept rate: 3%

 1 Your recurrence relation is: T(n)=(n-1)*T(n-1) + O(n) =(n-1)*((n-2)*T(n-2)+O(n-1)) + O(n) =(n-1)*((n-2)*((n-3)*T(n-3)+O(n-2))+O(n-1))+ O(n) =(n-1)*(n-2)*(n-3)*...1 + some O((n-2)!) + O(n) =O((n-1)!)  answered 22 Feb '18, 13:36 1.6k●2●9 accept rate: 23% 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
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,212
×349
×107
×90

question asked: 22 Feb '18, 12:43

question was seen: 308 times

last updated: 22 Feb '18, 21:05