Q:

run time analysis of the knapsack

I want to find the runtime of the following knapsack top-down approach algorithm in theta notation
KNAPSACK-TOP-DOWN(T, U )
     if U < 0 then return −∞
     else if T = ∅ or U = 0 then return 0
     else
         Let t = v, w be the last entry in T
         m1 ← KNAPSACK-TOP-DOWN(T − {t}, U )
         m2 ← v + KNAPSACK-TOP-DOWN(T − {t}, U − w)
         return max{m1 , m2 }

I believe the upper of the this problem is O(2^n). How to find the asymptotically tight bound? 

A:

Your pseudo-code represents the naive solution to the knapsack problem. See that it is structured much like the naive Fibonacci implementation which is O(2^n). And in fact the naive implementation of knapsack is exponential. Keep in mind that there is an Unbounded knapsack problem which can be solved in O(uT) with dynamic programming.
As for why this implementation is exponential, first, bear in mind that as T and U increases so does the number of recursive calls. Then notice that each iteration of the algorithm will recursively call KNAPSACK-TOP-DOWN twice, which, in the worst case scenario will call KNAPSACK-TOP-DOWN twice and so on.
                              (T, U)                                        1
                            /        \
                           /          \
                          /            \
                         /              \
                        /                \
              (T-{t},U)                    (T-{t},U-w)                      2
            /           \                /             \
           /             \              /               \
(T-{t}-{t'},U) (T-{t}-{t'},U-w)  (T-{t}-{t'},U-w) (T-{t}-{t'},U-w-w')       4
                                                                            8
                                                                            16
                                                                            ...

As you can see, the number of recursive calls grows exponentially according to the amount of items and capacity of the knapsack. Also notice that new elements in T will, in the worst case scenario, introduce a whole new "level" with twice as many computations as the previous level... This, of course, only happens if there is enough capacity left in the knapsack, so both T and U will influence the number of computations. Looking at the above tree it is clear that the naive implementation is indeed O(2^n).
But if you look attentively at the "stacktrace" you will notice that (T-{t}-{t'},U-w) (and consequently, all of its subproblems) is being called twice. This is where Dynamic Programming kicks in. We can store the computed results in some kind of data structure and further look them up so that the same subproblems don't need to be computed twice. When using this approach things drastically speed up and the whole problem can be computed in time proportional to the capacity of the knapsack * the amount of items to be considered, or, in theta notation, O(uT) 
This article provides C implementations of both the naive and the O(uT) versions. If your question is related to homework you should definitively take a look at it. Finally, searching for "Knapsack problem" will teach you a whole lot about NP-complete, NP-Hard, pseudo-polynomial time, and so on.

