Thread: *ANSWER* q5
View Single Post
Old 04-21-2013, 03:50 PM
yaser's Avatar
yaser yaser is offline
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,478
Default Re: *answer* q5

Originally Posted by OlivierB View Post
I would have a hard time coming up with a H that has exactly one of these growth functions, but why would that be impossible ? How can we be sure that no H can have that sort of growth function ?

The reason is that we proved that the growth function is either identically 2^N or else it has to be bounded above by a polynomial. The two excluded cases are faster than any polynomial, but still short of 2^N.
Where everyone thinks alike, no one thinks very much
Reply With Quote