#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

why we adding both and taking max???

can i  multiply both complexity and O(n^5) is correct??

please clear my doubt...

---

just tell me 

what is the complexity of the following code ?

int main() {
  //loop1
  for(int i=0; i< n ;i++) {
    printf("hie");
  }
  //loop2
  for(int i=0;i< n^2 ;i++) {
    printf("bye");
  }
  return 0;
}

---

@Debashish Can we use $\Theta$ here?

---

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