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..

general
, , ,
1

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<String, Integer> 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<String, Integer>();
            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;
    }

}
2

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)!)
1 Like
3

And yeah there will be no use of memoization here since there are n! States in ur recurrence.

4

@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

5

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.

1 Like
6

Memoisation just helps in avoiding recalculation of state.

7

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

8

Sorry i mean n! States