Justify the worst case for binary search. Find the edit distance from the string "RELEVANT" to "ELEPHANT" using dynamic programming approach. [5+0]

Binary search operates on a sorted array. It compares the target with the middle element. If they are unequal, half the array is discarded, and the process repeats on the remaining half. $$T(n) = T\left(\frac{n}{2}\right) + O(1), \quad T(1) = O(1)$$ The worst case occurs when: - the target is not...