2,575 views
1 votes
1 votes

I was reading some of the notes (made easy and ACE)  and noticed that some teacher have taught that time complexity for Binary Knapsack O(2^(n/2)). which can not be reduced further. but What I have seen here that in worst case by using memoization we can reduce the time complexity upto O(n.W) where n is number of Object and W is capacity of knapsack.

What I am thinking that, Is it really Binary knapsack is NPC, Like Travelling Salesman problem because TSP tales O(n^2*2^n) times to calculate the tour by using dynamic method, which is efficient than o(n^n) of TSP brutforce techniques? Put some light, Am I missing something. Should I stop seeing those notes which people have posted over the internet. 

1 Answer

Best answer
2 votes
2 votes

See AFAIK in DP we consider only the distinct function calls .So Using DP the complexity of Binary knapsack is O(nW).

But for the larger value of W the the complexity of Binary knapsack is O(2n). Because in 0/1 knapsack has very less repetition

So for the larger value W ,0/1 knapsack will generate n level complete binary tree So it will have  2n function calls and the time complexity

becomes O(2n). So it one of NP complete problem.

selected by

Related questions

1 votes
1 votes
1 answer
1
Rajnish Kumar asked Jan 17, 2017
892 views
given a N-bit string.what is the time complexity to find out all subsets of that string which is parlindrome?
11 votes
11 votes
5 answers
2
Vikrant Singh asked Dec 28, 2014
3,609 views
What is the complexity of finding $50^{th}$ smallest element in an already constructed binary min-heap?$\Theta(1)$$\Theta (\log n)$$\Theta (n)$$\Theta (n \log n)$
0 votes
0 votes
1 answer
3
highheels10 asked Sep 15, 2018
470 views
0 votes
0 votes
2 answers
4
radha gogia asked Jul 7, 2018
1,544 views
foo(int n) { for(int i=0 ; i<n ;i++) for(int j=i ; j<=i*i ;j++) if(j%i==0) { for(int k=0;k<j;k++) printf("hii"); } } How to proceed here for analyzing the time complexity...