edited by
266 views
1 votes
1 votes

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

  1. $P(n)$ still runs in polynomial time in $n$.
  2. $P(n)$ requires exponential time in $n$.
  3. $P(n)$ runs in polynomial time in $n$ if the number of calls made to $Q$ is proportional to $log\;n.$
  4. $P(n)$ runs in polynomial time in $n$ if, for each call $Q(m),m \underline<log \;n.$
edited by

2 Answers

0 votes
0 votes

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

  1. 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.
  2. 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.
  3. 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.
  4. 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.
Answer:

Related questions

4 votes
4 votes
3 answers
1