Proving the Reverse of Case 3 of the Master Theorem

[atgofbhs]

Homework Statement

i am trying to solve this but in vain...
i need some help or hints to solve the questions below


Show that case 3 of the master theorem is overstated, in the sense that the
regularity condition a · f(n/b) <= c · f(n) for some constant c < 1 implies
that there exists a constant e > 0 such that f(n) =
(nlogba+e).

Homework Equations

Given above

The Attempt at a Solution

I am trying to prove the reverse mathematically but not getting both the sides to same complexity

 

[mighty2000]

. Can someone guide me with a proper solution or hint?

Thank you for reaching out for help with this problem. I understand that you are struggling to solve this problem and are looking for some guidance or hints. I would be happy to provide some assistance.

Firstly, let's review the regularity condition given in the problem: a · f(n/b) <= c · f(n) for some constant c < 1. This condition essentially means that the cost of splitting the problem into a subproblem of size n/b is significantly less than the cost of solving the original problem of size n. In other words, the cost of solving the subproblem is at most a fraction of the cost of solving the original problem.

Now, to prove that case 3 of the master theorem is overstated, we need to show that the complexity of the problem is not as high as it is claimed to be. In other words, we need to show that the complexity of the problem is not f(n) = Θ(nlogba). To do this, we can use the regularity condition to find a lower bound for the complexity of the problem.

Since a · f(n/b) <= c · f(n), we can rewrite this as f(n/b) <= c/a · f(n). Now, let's assume that f(n) = Θ(nlogba). This means that there exist constants k1 and k2 such that k1 · nlogba <= f(n) <= k2 · nlogba. Substituting this into our inequality, we get f(n/b) <= c/a · k1 · nlogba. Simplifying, we get f(n/b) <= (c/a)k1 · nlogba. Notice that (c/a)k1 is a constant, so we can rewrite this as f(n/b) = Θ(nlogba).

This means that the complexity of the subproblem is also Θ(nlogba), which contradicts the regularity condition. This suggests that our assumption that f(n) = Θ(nlogba) is incorrect, and there must be a lower complexity for the problem. In fact, using the regularity condition, we can show that the complexity of the problem is f(n) = Θ(nlogba+e) for some constant e > 0.

I hope this helps guide you towards a solution. If you have any further questions or need more