Re: *ANSWER* q5
I'm having a hard time proving that functions iii) and iv) are not bounded by any polynomial in N (any idea or suggestion, would be appreciated). I found a very similar solution (I would like to know if it is correct):
If there exist a finite breakpoint k, then
(a) m_H(N) = 2^N for all N<k, and m_H(N) < 2^N for all N>=k
otherwise,
(b) m_H(N) = 2^N for all N
Functions iii) and iv) do not satisfy (b), so there must exist a finite k>=1 such that (a) is satisfied. Whatever this k be, we can check that for k>1, (a) is violated for N=1. And for k = 1 we must have a constant growth function, which is also not satisfied.
