Thread: Problem 2.8
View Single Post
Old 03-21-2018, 10:15 AM
k_sze k_sze is offline
Join Date: Dec 2016
Posts: 12
Default Re: Problem 2.8

Originally Posted by magdon View Post
The growth function cannot be any polynomial function of N. A valid growth function must satisfy the following theorem:

Theorem: If m(k)<2^k for some (any) k, then for all N, m(N)\le N^{k-1}+1.

In your example growth function below, try k=2 to show that the precondition of the theorem is satisfied with k=2 and hence deduce a linear bound on m(N). This contradicts the growth function being cubic. More generally, a cubic growth function cannot have a break point less than 4.
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.
Reply With Quote