Excellent explanation. I just want to add here at 13:05 the mathemathical part, the proof that O(log n) is true for Recherche Dichotomique: We have U(n) = 1+ U(n/2) (We assume that n is a power of 2. (n=2^k)) so U1 = 1 + U0 = 1 and U2 = 1 + U1 = 2 both of u1 and u2 satisfy Un = 1 + log(n) the base case of our induction, (log here is log base2) we continue to proceed by induction, assume that U(2^k) = 1+log(2^k) = 1+k then U(2^(k+1)) = 1+U(2^k) = 1+1+k = 1+log(2^(K+1)) and we have verified it for all power of 2.
Excellent explanation.
I just want to add here at 13:05 the mathemathical part, the proof that O(log n) is true for Recherche Dichotomique:
We have U(n) = 1+ U(n/2) (We assume that n is a power of 2. (n=2^k))
so U1 = 1 + U0 = 1
and U2 = 1 + U1 = 2
both of u1 and u2 satisfy Un = 1 + log(n) the base case of our induction, (log here is log base2)
we continue to proceed by induction,
assume that U(2^k) = 1+log(2^k) = 1+k
then U(2^(k+1)) = 1+U(2^k) = 1+1+k = 1+log(2^(K+1))
and we have verified it for all power of 2.