0
$\begingroup$

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$.

The answer here is: (d)

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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.$$

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.