4 ms·
Yeah, seems like the article implies an upper bound of 2^n for a greedy solution, so your example would be pretty bad with a worst case of 2^1000?
by alta22433 12y ago
Yeah, seems like the article implies an upper bound of 2^n for a greedy solution, so your example would be pretty bad with a worst case of 2^1000?
- Retric 12y agoMy example would be 1000 objects * 10,000 weights = 10,000,000 options. Which is much better than 2^(1000) ~= 10^300 for calculating every possibility, but still worse than n^2. For it to be worse you would need say 10 objects and 10,000 for max weight. so 2^n = 1024 vs n * k = 10 * 10,000 = 100,000