When the growth function = 2^N
Please elaborate a little bit more in the text why this is an issue. It is crucial that the bound be polynomial. So why is 2^N bad, but N^9999 good? :confused:

Re: When the growth function = 2^N
Quote:

Re: When the growth function = 2^N
Dear Professor,
Could you explain why you have chosen a polynomial? Could you have chosen another type of function, or series, for example? A sine or cosine? Thanks! 
Re: When the growth function = 2^N
Quote:

Re: When the growth function = 2^N
The polynomial is multiplied by a negative exponential. For any k>0, alpha, Lim_{x>\infinity} \alpha*p(x)*e^(kx) =0. On other for l>k, k>0, lim_{x>\infinity) e^(k*x)*e^(l*x) = \infinity

Re: When the growth function = 2^N
Quote:
In practice, we often don't have infinite , and so it might be that in some cases exponential isn't so bad. There are plenty of NP hard problems that can, in fact, be solved for practical (small ) cases. 
All times are GMT 7. The time now is 12:46 AM. 
Powered by vBulletin® Version 3.8.3
Copyright ©2000  2020, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. AbuMostafa, Malik MagdonIsmail, and HsuanTien Lin, and participants in the Learning From Data MOOC by Yaser S. AbuMostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.