Complexity of this code....

help
, ,
1

Solution… I am unable to know why this code is so fast when i feel like the complexity of this code is exponential… In contrast my dp solution with fast I/O is My solution… I know the complexity of my code that is (mn)… A quick reply is awaited

2

The complexity of recursive solution is exponential, in terms of 2^n= 2^20 operations at maximum which is nearly 10^6. Complexity of dp solution is sum X n which where sum can be at maximum (1000 X 20) as maximum value of every banknotes is 1000 and n can be at max 20. Thus, sumXn maximum will be 1000 X 20 X 20 which is nearly 4X10^6. Thus, the solutions are taking nearly the same time. Because you used fast i/o in dp one, it took little less. This is what I think and the possible reason is.

There was a very same problem in some contest, where the constraints were almost same and recursive solution took less time. Refer my solution to this problem, the recursive one took less time, which dp one took 0.46 sec.

2 Likes
3

I also thought this but actually what confused me was this question link text … I submitted this exponential solution for just checking and it was

int knapsack(int arr[],int sum,int n)
 {
if(n<0)return 0;
if(sum-arr[n]<0)
        return knapsack(arr,sum,n-1);
return max(knapsack(arr,sum-arr[n],n)+arr[n],knapsack(arr,sum,n-1));
 }

and it never timed out…

4

That is probably because, each element can be selected multiple times as per the question. So, the number of operations will be very large.

5

See my recursive implementation of the above here: https://www.hackerrank.com/challenges/unbounded-knapsack/submissions/code/2798511 It works fine for smaller test cases because complexity now is large.

6

Dudde see this code of mine … I dont think you gave me the right complexity coz 5 th test case has constraints upto 2000 https://www.hackerrank.com/challenges/unbounded-knapsack/submissions/code/2795566

7

Complexity for this solution is not the same as that of codechef one, look my solution for the complexity and the number of operations. My code gives timeout for 5th test case. I just wanted to show, that for the given constraints and complexity, the particular number of operations will not execute.

8

Then what is the complexity of the code on hacker rank