91
Example: Subset Sum
(cont)
Cost analysis:
C
i
= #calls to
subsetsum2()
for array of length i
for worst case,
C
1
= 2
C
n
= 3 + 2·C
n-1
⇒ C
n
≅ 2
n
Thus,
subsetsum2
is O(2
n
)
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}