View Single Post
  #2  
Old 07-29-2012, 03:09 PM
htlin's Avatar
htlin htlin is offline
NTU
 
Join Date: Aug 2009
Location: Taipei, Taiwan
Posts: 601
Default Re: Positive intervals

Quote:
Originally Posted by jianpan View Post
On book page 44, the growth function of positive intervals is defined as 2C(N+1). This is the fomular of selection without replacement, which implies we can't pick the same interval twice. But the book says " if the both end values fall in the same region, ....", which means we do allow to pick the same interval twice. If that's case, we should use selection with replacement N^2 in this case. This doesn't change the order of polynomial, but seems more rigorous.
The "if ..." part contributes to a single (constant) dichotomy, while the "selection without replacement" part contributes to C(N+1, 2) different dichotomies. If we directly use "selection with replacement" for counting the number of dichotomies, it would be an over-estimate of the growth function. Hope this helps.
__________________
When one teaches, two learn.
Reply With Quote