educative.io

How brute-force solution has complexity O(2 ^(N+C) )

Courses
,
#1

Can anyone please explain how brute-force solution has complexity O(2 ^(​N+C) ​) in case of unbounded knapsack top down(recursive) basic solution.

Thanks,
Ankush

1 Like
#2

The way how I understood it:

For regular Knapsack problem it’s O(2^N). Inside recursive function we do recursion twice, so we could visualize call stack as a binary tree (check the screen from the 0/1 Knapsack). To find number of nodes (recursive calls) we use formula (2^N+1) - 1 (asymptotically O(2^N)). In the unbound knapsack we have more items than N (as we can reuse them), so it’s equal O(2^N+X), where X is number of times we reused items. The sum of reused items (X) can’t be more than C (capacity), so if we reused the smallest item (worst case), it would be C/S (S - smallest item). In case if S == 1, like we have in the problem, C/S == C == X, so O(2^N+X) == O(2^N+C)

3 Likes
#3

@Eugene3

if we reused the smallest item (worst case), it would be C/S (S - smallest item). In case if S == 1, like we have in the problem, C/S == C == X, so O(2^N+X) == O(2^N+C)

If we selected the smallest element say 1, then 1 would be chosen C times. If so, then would N ever come into picture here ?? If we think about the recursion tree, the max length of this case ( depth of tree) would be equal to C. If N is greater then it would be N. So shouldn’t it be 2^ ( max of N , C) ?

#4

Consider a general scenario, where all the elements (2^N) have at least one repetition?
Here, the upper bound of the added up weights of any repeating element will never exceed ‘C’.
Hence the expression O(2^N+C)