Thread: Q4 and Q5
View Single Post
  #5  
Old 01-24-2013, 01:11 PM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,477
Default Re: Q4 and Q5

Quote:
Originally Posted by tathagata View Post
But doesn't lecture 6 discuss a more strict bound only if we have a break point? Whereas Q5 asks for any possible growth function, so being less than 2^N is sufficient I would have thought. What am i missing?
We either have a break point, or else we don't. In the latter case, the growth function is identically 2^N. In the former case, the growth function is constrained such that many formulas cannot possibly be valid growth functions.
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote