2
$\begingroup$

I know that the brute force method is not the best way to solve the 0-1 knapsack problem. I'm not quite getting the dynamic programming idea, but would like to know the following:

  • If the brute force method can solve the problem with 20 items in 1 second - how many items can it solve in one day (2^16 s)?

I know that the time complexity of brute force is big O(2^n). But still I don't see how I can solve this.

$\endgroup$
2
$\begingroup$

As O(2^n) says adding one item will double computation time, giving the fact that one day equals 2^16 seconds, you more or less answered the question yourself.

A method solving a problem with 20 items in 1 second will will solve a problem with 20 + 16 = 36 items in a day.

Wow, downvote for the right answer, that's nice! So let us elaborate on this:

Calculation 1

As we know worst-case runtime for 20 items is 1 second, there is no need to experiment and guess the constant factor (c) as suggested in another answer.

Instead we can get it by simple calculation:

1 second = c * 2^20 => c = 1/2^20 = 2^-20

The equation we still have to solve, to find out, with how many items we can expect an answer in a day is:

1 day =~ 2^16 seconds = c * 2^n = 2^-20 * 2^n

multiplied by 2^20 on both sides we end up with:

2^36 = 2^n

Which we might logarithmize on both sides, if we don't see, that n=36 directly.

qed.

Calculation 2

After verification of the answer 36, let's take a closer look at the alternative suggested - experimenting with 40 and 80 items*.

[*: at least before the author changed from these numbers to n_1 and n_2]

Expermient 1 - 40 items

For 40 items the algorith will take 2^20 times the time it takes for 20 items, and as such:

2^20 = 1048576 s = 17476 min = 291 h = 12 days

While waiting those 12 days for our calculation to complete, let's take a look at our second suggestion.

Expermient 2 - 80 items

For 80 items we will have to deal with 2^60 times the time it takes for 20 items:

2^60 = 1152921504606846976 s = 19215358410114116 min = 320255973501901 h = 13343998895912 days = 36558901084 years

As scientists estimate the age of our universe to be something around 13.7 * 10^9 years our result of something like 36.5 * 10^9 years seems to be rather ambitious.

Good luck waiting anyways.

naive c * 2^n Algorithm

There were doubts wether such an algorithm exists, so here a sample brute-force algorithm working in c * 2^n.

Written in pseudo code, so familarity with a specific programming language should not be required.

# let w[1], ... , w[n] be the weights of the items
# let v[1], ... , v[n] be the values of the items
# let maxWeight be the capacity of the knapsack

bestValue := 0

function solve(n, currentWeight, currentValue) {

    if n = 0 and currentWeight <= maxWeight and currentValue > bestValue:
        bestValue := currentValue

    if n = 0: return

    # don't pack this item
    solve(n-1, currentWeight, currentValue)
    # pack this item
    solve(n-1, currentWeight + w[n], currentValue + v[n])
}

solve(n, 0, 0)

print bestValue

Assignments and comporisons made in solve all run in O(1).

Recursion depth is n with 2 recursive calls in each run, resulting in 2^n runs total.

Runtime is thus not only bound by O(2^n), but also of the form c*2^n as requested.

qed.

Answering still open questions

... taken from the comments section

1) How do you check a solution candidate in O(1) time? 2) Even the most naive algorithm may find a witness early and abort. 3) How do you make the jump from some abstract, unspecified combinatoric measure to runtime (in seconds)?

ad 1: O(1) time candidate check in the pseudo code example takes place in line 9:

if n = 0 and currentWeight >= maxWeight and currentValue > bestValue: bestValue := currentValue

ad 2: It indeed may

... if you are lucky or at least not very unlucky. Nevertheless there is no guarantee.

ad 3: The "jump" to computation time in seconds takes into account the trustworthyness of the information that

the brute force method can solve the problem with 20 items in 1 second

... (on a specific machine) given in the exercise, reading "the problem" as a synonym for the 0-1 knapsack problem, which, at least as I read it, should include all problem instances, even the ones taking worst-case time.

$\endgroup$
  • $\begingroup$ This is a naive calculation that assumes that the runtime is $= c \cdot 2^n$ for all $n$ -- it is not. (That is, the rough $O(2^n)$ bound given in the question -- which is unlikely to be correct, anyway -- does not imply it.) $\endgroup$ – Raphael Nov 14 '14 at 18:02
  • $\begingroup$ The most naive brute-force implementation should be even Θ(2^n) as any of the 2^n combinations has to be checked resulting in c⋅2^n in this case. Branch pruning and more clever implementation strategies might reduce this to O(2^n). Nevertheless worst-case runtime will still be of the form c*2^n. $\endgroup$ – mikyra Nov 14 '14 at 18:09
  • $\begingroup$ 1) How do you check a solution candidate in $O(1)$ time? 2) Even the most naive algorithm may find a witness early and abort. 3) How do you make the jump from some abstract, unspecified combinatoric measure to runtime (in seconds)? $\endgroup$ – Raphael Nov 14 '14 at 18:38
  • $\begingroup$ A sample c*2^n algorithm has been added. $\endgroup$ – mikyra Nov 14 '14 at 19:26
  • $\begingroup$ @user66875 The answer below by Raphael is correct. Big-o simply gives the worst case asymptotic runtime $\endgroup$ – 1110101001 Nov 15 '14 at 1:16
4
$\begingroup$

You can't. Landau notation does not hold enough information.

  • You don't know the constant factor(s).
  • With only $O$, you don't have a lower bound.
  • It's only a worst-case bound; different runs with the number of items can have wildly different runtimes.
  • Such bounds only hold in the limit, that is even $\leq c \cdot 2^n$ may not hold for those $n$ you can realistically run the algorithm for.
  • The quantity bounded is not runtime but some abstract measure.

    In particular, effects like operation reordering, memory hierarchy and branch mispredictions routinely skrew with runtimes.

The best you can do is assume that the runtime behaves like $\approx c \cdot 2^n$, run experiments with $n_1$ and $n_2$ items and estimate the constant factor -- then it's simple rule of three. But given all the caveats listed above, the prediction is unlikely to be worth much.

$\endgroup$
  • $\begingroup$ Thanks Raphael, but I think there should be a way as this was a question in an exam, I simply don't have the solutions. $\endgroup$ – user66875 Nov 14 '14 at 11:30
  • $\begingroup$ While true that different runs with different number of items and different items can have wildly different runtimes, though sure open to interpretation, I'd read the given the question "how many items can it solve in one day?" as "how many items can it _guaranteed_ solve in one day?". Which is a question of worst-case runtime, for which the upper bound gives enough information. $\endgroup$ – mikyra Nov 14 '14 at 18:24
  • $\begingroup$ @user66875 Um...if I was a professor, I would totally put a trick question in about this to see if the kids actually get what O notation is, and more importantly what it isn't. We can all write a O(n) sorting algorithm, but the overhead makes it impractical in most cases. A single point measurement of an algorithm can NEVER give you exact run times of larger computation. $\endgroup$ – IdeaHat Nov 14 '14 at 20:06
  • $\begingroup$ Well, not all of us can. At least regarding comparison based sorting I still fail even to write an algorithm beating Ω(n log n) and still haven't found the failure in the proof telling this is the best I will ever be able to get. $\endgroup$ – mikyra Nov 15 '14 at 2:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.