Since, at each step the size of the (searchable) array is reduced to half (1/2), we could write the following recurrence relation for the Binary Search Algorithm
Binary Search is a divide and conquer algorithm that finds a particular element within a sorted array or a given integer range.
Strassen’s Algorithm for Matrix multiplication is a recursive algorithm for multiplying n x n matrices in ie time. It outperforms the naive matrix multiplication algorithm. Naive Matrix-Multiplication (A, B) Pseudocode 1. n = Length[A] 2. C = n x n matrix 3. for i = 1 to n 4. do for […]
Quicksort is a sorting algorithm whose worst-case running time is O(n^2), for an input of size n. Quicksort, in spite of having worse time complexity than Merge Sort which is O(nlogn), it is a better practical choice for sorting. This is because it is remarkably efficiently on average cases, where its […]