Thread: Problem 2.8
View Single Post
  #5  
Old 03-22-2018, 03:08 AM
htlin's Avatar
htlin htlin is offline
NTU
  
Join Date: Aug 2009
Location: Taipei, Taiwan
Posts: 601
Default Re: Problem 2.8
Quote:
Originally Posted by k_sze View Post
To show that a growth function is invalid, is it sufficient to do this?
  1. Determine the smallest k where m_\mathcal{H}(k+1) < 2^{k+1}, such that k would be our d_{\text{vc}} if the growth function were valid;
  2. Find any concrete value of N where one of the inequalities vs m_\mathcal{H}(N) is violated.
Sounds reasonable to me.
__________________
When one teaches, two learn.
Reply With Quote