Complexity of Algorithms

This lecture covers the complexity of algorithms, including linear and dichotomous search algorithms, the concept of complexity order, and the evaluation of computational cost. It delves into the evaluation of cost calculations for different algorithms, such as insertion sorting and linear search. The lecture also explores the importance of clear problem specifications, the effectiveness of algorithms in various cases, and the comparison of algorithm complexities using notations like O(n). Additionally, it discusses the dichotomy search algorithm, its recursive nature, and the evaluation of its computational cost. The lecture concludes with examples and comparisons of algorithm complexities to understand their performance.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related lectures (40)

Related concepts (48)

CS-119(c): Information, Computation, Communication

L'objectif de ce cours est d'introduire les étudiants à la pensée algorithmique, de les familiariser avec les fondamentaux de l'Informatique et de développer une première compétence en programmation (

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning), achieving automation eventually.

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.

Search algorithm

In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with either discrete or continuous values. Although search engines use search algorithms, they belong to the study of information retrieval, not algorithmics. The appropriate search algorithm to use often depends on the data structure being searched, and may also include prior knowledge about the data.

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.

Linear search

In computer science, linear search or sequential search is a method for finding an element within a list. It sequentially checks each element of the list until a match is found or the whole list has been searched. A linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the list. If each element is equally likely to be searched, then linear search has an average case of n+1/2 comparisons, but the average case can be affected if the search probabilities for each element vary.

Algorithmic Complexity: Definition and Examples CS-119(d): Information, Computation, Communication

Explores algorithm correctness, worst-case complexity analysis, and efficiency comparison based on input size.

Solving Parity Games in Practice

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

Complexity & Induction: Algorithms & Proofs CS-101: Advanced information, computation, communication I

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

Algorithm Complexity: Search and Analysis CS-119(c): Information, Computation, Communication

Delves into algorithm complexity, analyzing search efficiency and operation count, with a focus on worst-case scenarios and 'big O' notation.

Recursive Algorithms: Induction & Sorting CS-101: Advanced information, computation, communication I

Explores induction, recursion, and sorting algorithms, including merge sort and the proof of correctness for recursive algorithms.