Problem 2.8

[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?

[magdon]

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.

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?

[axelrv]

thanks!

[k_sze]

Originally Posted by magdon

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.

To show that a growth function is invalid, is it sufficient to do this?

1. Determine the smallest where , such that would be our if the growth function were valid;
2. Find any concrete value of where one of the inequalities vs is violated.

[htlin]

Originally Posted by k_sze

To show that a growth function is invalid, is it sufficient to do this?

1. Determine the smallest where , such that would be our if the growth function were valid;
2. Find any concrete value of where one of the inequalities vs is violated.

Sounds reasonable to me.