sec recurrence relations we can deduce from this expansion that this recurrence is equivalent to following summation and its derivationf ( <log - + log( / = log - (log ii= log log - - = log - - = log log log log divide and conquer recurrences the third approach to solving recurrences is to take advantage of known theorems that describe the solution for classes of recurrences one useful example is theorem that gives the answer for class known as divide and conquer recurrences these have the form (nat( /bcnk ( where abcand are constants in generalthis recurrence describes problem of size divided into subproblems of size /bwhile cnk is the amount of work necessary to combine the partial solutions mergesort is an example of divide and conquer algorithmand its recurrence fits this form so does binary search we use the method of expanding recurrences to derive the general solution for any divide and conquer recurrenceassuming that bm (na(at( / ( / ) cnk am ( am- ( /bm- ) ac( / ) cnk am- bik = ca = (bk / )