Keep in mind that only one of the recursive calls will happen! Also, L[:n/2] is the first half of the list, and L[n/2:] is the second half of the list.

6. Use the Master Theorem to find the complexity of Binary Search. Specifically, if L is already sorted: binary Search (L, val): n = len (L) if n= 1 && L[0] val: return True if val