Thread: *ANSWER* q5
View Single Post
Old 04-21-2013, 02:55 PM
OlivierB OlivierB is offline
Join Date: Apr 2013
Location: Paris
Posts: 16
Default *ANSWER* q5

I see why i, ii, v are possible formulae for growth functions: We have seen examples in class.

But I don't see why iii and iv are not possible formulae for growth functions too, since both this quantities are smaller than the maximum i.e. 2^N (obviously in the case of iv for all N; and in the case of iii for N large - ok, I have not checked for all N).

Of course I would have a hard time coming up with a H that has exactly one of these growth functions, but why would that be impossible ? How can we be sure that no H can have that sort of growth function ?
I must have missed something..

Even if this type of consideration has little practical consequences, I would be interested to know.
Reply With Quote