master theorem

dividing functions

to solve a recurrence relation of the form:
we compare with and check which one dominates, the possible outcomes are:

example of the first possibility
the conditions of the first possibility are met:
therefore we get:

example of the second possibility
the conditions of the second possibility are met:
we get:

im not sure whether this example is correct

example of the third possibility
the conditions of the third possibility are met:
we get:

decreasing functions

the master theorem can be used to solve recurrences of the form , where and and is asymptotically positive. (asymptotically positive means that the function is positive for all sufficiently large n.) this recurrence describes an algorithm that divides a problem of size into sub problems, each of size , and solves them recursively.
the theorem is as follows:
if , where , , and
we consider 3 cases:
case 1, if