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$?
- $P(n)$ still runs in polynomial time in $n$.
- $P(n)$ requires exponential time in $n$.
- $P(n)$ runs in polynomial time in $n$ if the number of calls made to $Q$ is proportional to $\log\;n.$
- $P(n)$ runs in polynomial time in $n$ if, for each call $Q(m),m \underline<\log \;n.$