Divide and Conquer a problem into a sub-problem to solve it efficiently Assume that problem A cannot be solved in O(n^2) time. However, we can transform problem A into a problem B in O(n^2 log n) time, and then solve B, and finally transform the solution of B into the solution of A in O(n) time.

Prove or Disprove: The above approach shows that problem B cannot be solved asymptotically less than O(n^2) time.



My Answer-> 

Let time complexity (TC) of B be h(n). 
So overall complexity is maximum of(h(n), n²logn) which will be greater or equal
to n²logn greater than n² considering the highest polynomial term.

Ω(f(n)) ≥ { g(n) : there exists c &gt; 0 and n0 such that g(n) ≤ c.f(n) for all n &gt; n0 }.

Here f(n) is O(n2logn+n) and g(n) is O(n2logn) which satisfy the above condition at c&gt;=1 and n0 = 0

(n^2 log n) &lt; 1*(n^2logn+n) for all n &gt; 0

So lower bound of solution B is g(n) i.e. O(n^2logn)

So B cannot be solved asymptotically less than O(n^2 log n) time

Therefore B cannot be solved asymptotically less than O(n^2) time
The given information tells you absolutely nothing about the runtime of B. 

As an example, let’s say the solution is a vector of N numbers which can be found in O(n^2 log n) but not in O(n^2), and let B be the problem “What was your input”. Solve the problem in O(n^2 log n), pass the solution to B, get it back in O(n), all consistent with the information you have.