# How can a $P(n)$ run in polynomial time if it calls $R(m)$ which has exponential time

We have a procedure $$P(n)$$ that makes multiple calls to a procedure $$Q(m)$$, and runs in polynomial time in n. Unfortunately, a significant flaw was discovered in $$Q(m)$$, and it had to be replaced by $$R(m)$$, which runs in exponential time in m. Thankfully, P is still correct when we replace each call to $$Q(m)$$ with a call to $$R(m)$$ instead. Which of the following can we definitely say about the modified version of P?

(a) $$P(n)$$ still runs in polynomial time in $$n$$.

(b) $$P(n)$$ requires exponential time in $$n$$.

(c) $$P(n)$$ runs in polynomial time in $$n$$ if the number of calls made to Q is proportional to $$log n$$

(d) $$P(n)$$ runs in polynomial time in $$n$$ if, for each call $$Q(m)$$, $$m ≤ log n$$.

Their reasoning: If $$m ≤ log n$$ for each call to $$Q$$ with argument $$m$$, then the running time of $$R(m)$$ is exponential in $$m$$ but polynomial in $$n$$. Since the number of calls to $$Q$$ originally (and $$R$$ after the modification) is a polynomial in $$n$$, the overall running time of $$P$$ is polynomial. None of the other options definitively hold

I don't understand how they reached that conclusion: Since $$R(m)$$ is exponential, calling it even once would result into exponential time and since $$R(m)$$ is a sub-routine to $$P(n)$$, how can they say that "running time of $$R(m)$$ is exponential in m but polynomial in $$n$$"

I am totally confused by this, i can understand reductions ( Theory of computation ), my assumption was according to programming if we call an exponential function inside a polynomial function. The overall complexity would be exponential since that is the bottle-neck

Can someone shed a light on how to approach these problems?

If $$R(n)$$ is exponential in $$n$$, $$R(\log n)$$ is polynomial in $$n$$.
E.g. $$T(n)=4^n\to T(\log_2n)=4^{\log_2n}=n^2.$$
If $$R(m)$$ runs in exponential time in $$m$$, that means that the running time of $$R(m)$$ is, informally, something like $$O(2^m)$$. More formally, its running time is $$O(c^m)$$ for some constant $$c$$.
Now plug in $$m=\log n$$, simplify, and see what conclusions you can draw about the running time as a function of $$n$$.