#Day16 #100DaysOfCode
the master theorem is used in calculating the time complexity of a recurrence relation.
where a is the number of subproblems in all recursive calls
n/b: size of each subproblem, assuming all subproblems are of same size (i.e: n/2, a subproblem is half an input)
f(n): cost of work done outside recursive calls, including cost of dividing problems and merging solutions.
find a, b, logaofb. if larger, smaller, or equal to the exp of n in f(n) falls into one of the categories below.
the master theorem is used in calculating the time complexity of a recurrence relation.
where a is the number of subproblems in all recursive calls
n/b: size of each subproblem, assuming all subproblems are of same size (i.e: n/2, a subproblem is half an input)
f(n): cost of work done outside recursive calls, including cost of dividing problems and merging solutions.
find a, b, logaofb. if larger, smaller, or equal to the exp of n in f(n) falls into one of the categories below.
