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.
Quote:
Originally Posted by axelrv
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?
|