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.

+1

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

+2

**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.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 488
- Exam Queries 436
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,203 questions

43,662 answers

124,116 comments

42,944 users