divide and conquer

Divide And Conquer

fib(n) = fib(n-1) + fib(n+2)

Merge Sort
                    3,5,2,7,1,4,0,6
                      /          \
                   3,5,2,7    1,4,0,6
                     |            |
                   2,3,5,7    0,1,4,6
                     \            /
                    0,1,2,3,4,5,6,7

                T(n) = 2*T(n/2) + n  ==>  O(n log n)

Decrease and Conquer vs Divide and Conquer

                 how much smaller
# subproblems      n-1    n/2
           1                      decrease and conquer
          2+                      divide and conquer

=====

def sum(a: Array[Int]): Int = {
	def s(lo: Int, hi: Int): Int = {  // hi is inclusive
		// if(hi < lo) 0
		//else
		if(lo == hi) a(lo)
		else {
			val mid = (lo+hi+1)/2
			s(lo, mid) + s(mid+1, hi)
		}
	}
	if(a.isEmpty) 0
	else s(0, a.length-1)
}

     T(n) = 2*T(n/2) + 1  ==>  O(n)