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.1k
- Engineering Mathematics 4k
- Digital Logic 1.7k
- Programming & DS 3k
- Algorithms 2.6k
- Theory of Computation 3.2k
- Compiler Design 1.2k
- Databases 2.4k
- CO & Architecture 2.1k
- Computer Networks 2.4k
- Non GATE 819
- Others 1.1k
- Admissions 244
- Exam Queries 420
- Tier 1 Placement Questions 16
- Job Queries 39
- Projects 4

29,157 questions

36,984 answers

92,154 comments

34,823 users