#made easy

Question

suppose a problem A reduces to problem B & reduction is done at $O(n^2)$ time.

if the problem is solved in $O(n^3)$ time then what about the time of problem A___??

• A. $O(n^2)$
• B. $O(n^3)$
• C. $O(2^n)$
• D. $O(n^5)$

Answer 1

Total problem : step(1) REDUCTION => $O(n^2)$ , and step(2) Solve => $O(n^3)$

T(n) = $O(n^2) + O(n^3) = O(n^3)$

so, 2. $O(n^3)$

Comments

Sir, I think we can not guarantee the minimum comlexity of solving(step2). so, can not write overall theta($n^3$). correct me if wrong

---

yes, exactly.

---

understand the concept thnx