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

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;
    }

}

asked 22 Feb '18, 12:43

hemant_dhanuka's gravatar image

5★hemant_dhanuka
533112
accept rate: 3%

edited 22 Feb '18, 20:53


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)!)
link

answered 22 Feb '18, 13:36

vivek_1998299's gravatar image

6★vivek_1998299
1.6k29
accept rate: 23%

edited 22 Feb '18, 13:37

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

(22 Feb '18, 16:29) vivek_19982996★

@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) hemant_dhanuka5★
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) vivek_19982996★

Memoisation just helps in avoiding recalculation of state.

(22 Feb '18, 20:49) vivek_19982996★

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) hemant_dhanuka5★

Sorry i mean n! States

(22 Feb '18, 21:05) vivek_19982996★
showing 5 of 6 show all
toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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