Thread: *ANSWER* q5
View Single Post
  #8  
Old 10-19-2021, 06:40 AM
noslen noslen is offline
Junior Member
 
Join Date: Oct 2021
Posts: 1
Default 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.
Reply With Quote