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:
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:
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
