Thread: Problem 2.8
View Single Post
Old 10-10-2012, 08:52 AM
magdon's Avatar
magdon magdon is offline
Join Date: Aug 2009
Location: Troy, NY, USA.
Posts: 597
Default 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 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.

Originally Posted by axelrv View Post
I thought that growth functions could take on any polynomial function of N, so why is 1 + N + N(N-1)(N-2) / 6 not a possible growth function?
Have faith in probability
Reply With Quote