divide and conquer

1divide and conquer: 
2  split the problem into sub problems, 
3  solve each sub problem to eventually solve the main problem

1T(n) = aT(n/b) + f(n),
2where,
3n = size of input
4a = number of subproblems in the recursion
5n/b = size of each subproblem. All subproblems are assumed to have the same size.
6f(n) = cost of the work done outside the recursive call, which includes the cost of dividing the problem and cost of merging the solutions
7
8

1DAC(a, i, j)
2{
3    if(small(a, i, j))
4      return(Solution(a, i, j))
5    else 
6      m = divide(a, i, j)               // f1(n)
7      b = DAC(a, i, mid)                 // T(n/2)
8      c = DAC(a, mid+1, j)            // T(n/2)
9      d = combine(b, c)                 // f2(n)
10   return(d)
11}