Find the Asymptotic Bounds
a)
Consider the following recurrence:
Apply the master theorem and compare this recurrence with
From the specified recurrence, a = 2 and b = 4.
Calculate 
as shown
below:
Therefore, 
And 
Hence, 
Therefore, Case-1 of the master theorem can be applied as the solution.
Thus, the solution is, 
b)
Consider the following recurrence:
Apply the master theorem and compare this recurrence with
From the specified recurrence, a = 2 and b = 4.
Therefore,
And 
Hence, 
Therefore, Case-2 of the master theorem can be applied as the solution.
Thus, the solution is, 
c)
Consider the following recurrence:
Apply the master theorem and compare this recurrence with
From the specified recurrence, a = 2 and b = 4.
Therefore, 
And 
Hence, 
Therefore, Case-3 of the master theorem can be applied as the solution.
Thus, the solution is, 
d)
Consider the following recurrence:
Apply the master theorem and compare this recurrence with
From the specified recurrence, a = 2 and b = 4.
Therefore,
And 
Hence,
Therefore, Case-3 of the master theorem can be applied as the solution.
Thus, the solution is, 
Refer the Theorem 4.1 (Master Theorem) given on page 94 of chapter 4. In this theorem, it is defined that the recurrence will be solved by the mater theorem, if it is in any form of the three cases.
Now consider the given recurrence
.
Here,
then,
.
Therefore,
Check the first and second cases of master theorem:
• For the given recurrence, the
function 
• Now, it can easily bees seen that 
or 
• Also, 
or
.
So, it does not form the first and the second cases.
Check third case of master theorem:
Here, is
asymptotically greater than 
but not
polynomial greater or larger.
This is the main criteria of the third case. So, the
recurrencedoes not
form the third case.
Hence, from the above explanation, the recurrencedoes not
form the any of the three cases of master method.
Therefore, it is not possible to apply master method on the
recurrence
.
Apply the substitution method and guess the solution.
The substitution techniques requires to guess the solution by
assuming that:
Substitution into the recurrence yields:
Here, the value of lg 2 is constant so it can be ignored.
Hence, an asymptotic upper bound for the recursion
is 
Regularity condition in Master theorem is 
for some
constant,
.
Refer Theorem 4.1 of text book for Master theorem.
Define a piecewise function 
as
follows:
Consider a = 3 and b = 2 (here, 
).
There exists an, such that both cases of holds.
Therefore, the function satisfies
all the conditions except regularity condition.
Verify whether the function satisfies the regularity condition or not.
If 
, then
.
Since, for any number d, there always exists a number
(example
).
Also,
when n >> b (n is too larger than
b).
The function does not
satisfy the regularity condition for large n, such that
is
an integer.
Therefore, this is a required function , that
satisfies all the conditions in the case 3 of the master theorem,
except the regularity condition.