We’ll assume P(n) calls Q(m) or R(m) k times, and prove the claims to be right or wrong below:-
Note:- O(P(n))=O(k*R(m)) or O(k*2^m)……..(1)
where k=# calls made to R(m), also k must be upper bounded by a polynomial function of n, else the original function wouldn’t have been polynomial in n
- Claims that P(n) runs in polynomial time in n, we can easily substitute m=n in (1) to see that it clearly runs in exponential time in n.
- Claims that P(n) runs in exponential time in n, if we substitute m to be log(n) in (1), the complexity becomes O(k*n), which can be said to run in polynomial time.
- if k is proportional to log(n) or( k=c*log(n)), complexity becomes O(log(n)*2^m), here m can again be substituted to be n and it violates the claim in this statement.
- if m<=log(n), by taking the worst case i.e m=log(n) and putting it in O(k*2^m) we can see the ans is O(k*n) which we can safely say to be polynomial.