Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Recursion and Karatsuba Multiplication

Description

This lecture covers the concept of recursion in algorithms, focusing on the general case and the specific case of merge sort. It also explains the Karatsuba multiplication method for efficiently multiplying large numbers, demonstrating the algorithm step by step.

Official source

Ontological neighbourhood

Theoretical computer science

Algorithms and data structures: Analysis of algorithms

Related concepts (19)

Merge sort

In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the relative order of equal elements is the same in the input and output. Merge sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up merge sort appeared in a report by Goldstine and von Neumann as early as 1948.

Sorting algorithm

In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output.

Merge algorithm

Merge algorithms are a family of algorithms that take multiple sorted lists as input and produce a single list as output, containing all the elements of the inputs lists in sorted order. These algorithms are used as subroutines in various sorting algorithms, most famously merge sort. The merge algorithm plays a critical role in the merge sort algorithm, a comparison-based sorting algorithm.

Divide-and-conquer algorithm

In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. The divide-and-conquer technique is the basis of efficient algorithms for many problems, such as sorting (e.g., quicksort, merge sort), multiplying large numbers (e.

External sorting

External sorting is a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory, usually a disk drive. Thus, external sorting algorithms are external memory algorithms and thus applicable in the external memory model of computation. External sorting algorithms generally fall into two types, distribution sorting, which resembles quicksort, and external merge sort, which resembles merge sort.

Related lectures (30)

Merge Sort: Divide and Conquer

Explores the Merge Sort algorithm, applying the Divide and Conquer approach to sorting arrays efficiently.

Merge Sort: Sorting Algorithm

Explains the merge sort algorithm, its correctness, and time complexity compared to other sorting algorithms.

Solving Recurrences

Focuses on solving recurrences in divide-and-conquer algorithms using various techniques and examples.

Complexity & Induction: Algorithms & Proofs

Covers worst-case complexity, algorithms, and proofs including mathematical induction and recursion.

Divide-and-Conquer: Merge Sort