Question

Assume that a problem A cannot be solved in O(n²) time. However, we can transform A into a problem B in O(n² log n) time, and then solve B, and finally transform the solution of B in O(n) time into a solution for A.

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

Answer 1

Given:

a) A cannot be solved in O(n²).

b) B can be solved in O(n²logn) and solution from B can be transformed in O(n) time.

Proof:

Total complexity of solution while solving problem using B is: Time complexity of Solution B + Time complexity of solution transformation from B

Time complexity of  solving problem using B = O(n²logn)+O(n) = O(n²logn+n)

Consider the omega notation of time complexity for lower bound

(Source: Tutorialpoints)

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

Here f(n) is O(n²logn+n) and g(n) is O(n²logn) which satisfy the above condition at c>=1 and n₀ = 0

n²logn < 1*(n²logn+n) for all n>0

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

So B cannot be solved asymptotically less than O(n²logn) time

Therefore B cannot be solved asymptotically less than O(n²) time