The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+1 vote

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.

+2 votes

Best answer

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(2^{n}). 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 2^{n} function calls and the time complexity

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

@ManojK Can you explain more, What do you mean by larger value? and Why that O(nW) did not work in the larger value?

**for n=5, W=100000 **Here w has larger value.

Here n is polynomial in length but length of w not polynomial it can anything.

**When comparing this with the brute force algo take O(2**^{n}**), but depending on W, either the dynamic programming algorithm is more efficient or the brute force algorithm could be more efficient. (For example, for n=5, W=100000, brute force is preferable, but for n=30 and W=1000, the dynamic programming solution is preferable.)**

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 284
- Exam Queries 398
- Tier 1 Placement Questions 17
- Job Queries 51
- Projects 7

33,712 questions

40,256 answers

114,368 comments

38,885 users