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

Lecture

Problem-solving Strategies: Sum of Integers (Recursive) Complexity

Description

This lecture revisits complexity and calculates the complexity of a recursive algorithm to find the sum of the first integers, discussing the worst-case scenario, function dependencies, and the equivalence between recursive and iterative complexities.

Official source

Related concepts (15)

Computational complexity theory

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used.

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Analysis of algorithms

In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that relates the size of an algorithm's input to the number of steps it takes (its time complexity) or the number of storage locations it uses (its space complexity). An algorithm is said to be efficient when this function's values are small, or grow slowly compared to a growth in the size of the input.

Average-case complexity

In computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs. It is frequently contrasted with worst-case complexity which considers the maximal complexity of the algorithm over all possible inputs. There are three primary motivations for studying average-case complexity.

Equivalence relation

In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relation provides a partition of the underlying set into disjoint equivalence classes. Two elements of the given set are equivalent to each other if and only if they belong to the same equivalence class.

Related lectures (25)

Solving Parity Games in Practice

Explores practical aspects of solving parity games, including winning strategies, algorithms, complexity, determinism, and heuristic approaches.

Matrix Multiplication and Divide-and-Conquer Techniques

Discusses matrix multiplication using divide-and-conquer techniques and introduces Strassen's algorithm for improved efficiency.

Dynamic Programming: Binomial Coefficients Calculation Complexity

Explores the complexity of calculating binomial coefficients using dynamic programming.

Dynamic Programming: Rod Cutting and Matrix Chain Multiplication

Covers dynamic programming techniques for solving the rod cutting and matrix chain multiplication problems.

Complexity of Algorithms