CMI2020-A: 10

Question

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 \underline<log \;n.$

Comments

If a procedure makes multiple calls to another procedure, the running time of the first procedure is determined by the running time of the second procedure and the number of calls made to it. If the second procedure runs in exponential time, it is unlikely that the first procedure will still run in polynomial time, regardless of the number of calls made to the second procedure. Therefore, the modified version of the procedure most likely requires exponential time to run.

Answer 1

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

• A. 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.
• B. 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.
• C. 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.
• D. 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.

Comments

How are you replacing value of m in (1) for options C and D ?

(1) corresponds to complexity of R(m) (i.e., 2^m), and option C and D has calls of Q(m), whose complexity is not exponential (as P(n) ran in polynomial time when it called Q(m) in first scenario)

Answer 2