
#1




Problem 2.8
I thought that growth functions could take on any polynomial function of N, so why is 1 + N + N(N1)(N2) / 6 not a possible growth function?

#2




Re: Problem 2.8
The growth function cannot be any polynomial function of N. A valid growth function must satisfy the following theorem:
Theorem: If for some (any) , then for all N, . In your example growth function below, try to show that the precondition of the theorem is satisfied with 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.
__________________
Have faith in probability 
#3




Re: Problem 2.8
thanks!

#4




Re: Problem 2.8
Quote:

#5




Re: Problem 2.8
Sounds reasonable to me.
__________________
When one teaches, two learn. 
Thread Tools  
Display Modes  

