Concept

Probabilistic analysis of algorithms

In analysis of algorithms, probabilistic analysis of algorithms is an approach to estimate the computational complexity of an algorithm or a computational problem. It starts from an assumption about a probabilistic distribution of the set of all possible inputs. This assumption is then used to design an efficient algorithm or to derive the complexity of a known algorithm. This approach is not the same as that of probabilistic algorithms, but the two may be combined. For non-probabilistic, more specifically deterministic, algorithms, the most common types of complexity estimates are the average-case complexity and the almost-always complexity. To obtain the average-case complexity, given an input distribution, the expected time of an algorithm is evaluated, whereas for the almost-always complexity estimate, it is evaluated that the algorithm admits a given complexity estimate that almost surely holds. In probabilistic analysis of probabilistic (randomized) algorithms, the distributions or average of all possible choices in randomized steps is also taken into account, in addition to the input distributions.

Official source

https://en.wikipedia.org/wiki/Probabilistic_analysis_of_algorithms

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 courses (1)

COM-401: Cryptography and security

This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how they work and sketch how they can be implemented. ...

Related lectures (7)

Matrix Multiplication and Divide-and-Conquer Techniques

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

Model-Free Prediction in Reinforcement Learning: Key Methods

Covers model-free prediction methods in reinforcement learning, focusing on Monte Carlo and Temporal Differences for estimating value functions without transition dynamics knowledge.

Dynamic Programming: Rod Cutting and Matrix Chain Multiplication

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

Related publications (12)

Search for the rare \(B^+ \rightarrow K^+ \tau^+ \tau^-\) decay with the LHCb experiment

We search for the rare B+ -> K+ tau+ tau- decay using data collected by the LHCb detector at a centre-of-mass energy of 13 TeV during the years 2016-2018, corresponding to a total integrated luminosity of 5.4 fb-1. The two tau leptons are reconstructed through their decay, tau -> pi+ pi- pi+ (pi0) nu. We develop a new method to fit the B+ -> K+ tau+ tau- decay chain in order to recover the missing information from the neutrinos and obtain a refitted B mass whose resolution is 100 MeV better than the one obt

EPFL2026

Multilevel quadrature formulae for the optimal control of random PDEs

Fabio Nobile

This manuscript presents a framework for using multilevel quadrature formulae to compute the solution of optimal control problems constrained by random partial differential equations. Our approach consists in solving a sequence of optimal control problems discretized with different levels of accuracy of the physical and probability discretizations. The final approximation of the control is then obtained in a postprocessing step, by suitably combining the adjoint variables computed on the different levels. W

Springer2025

TopoTome: Topology-informed unsupervised segmentation and analysis of 3D images

Biological systems are three-dimensional and complex. Today, images of biological structures can be acquired using different imaging technologies and at increasing resolutions. However, identifying relevant structural features in three-dimensional (3D) images remains a significant challenge. 3D image segmentation is usually performed using deep-learning segmentation models. Such models are trained on manually annotated and segmented, dataset-specific images. Consequently, they rarely generalize across datas

bioRxiv2025

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Official source

https://en.wikipedia.org/wiki/Probabilistic_analysis_of_algorithms

About this result

Related courses (1)

COM-401: Cryptography and security

Related lectures (7)

Matrix Multiplication and Divide-and-Conquer Techniques

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

Model-Free Prediction in Reinforcement Learning: Key Methods

Covers model-free prediction methods in reinforcement learning, focusing on Monte Carlo and Temporal Differences for estimating value functions without transition dynamics knowledge.

Dynamic Programming: Rod Cutting and Matrix Chain Multiplication

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

Related publications (12)

Search for the rare \(B^+ \rightarrow K^+ \tau^+ \tau^-\) decay with the LHCb experiment

EPFL2026

Multilevel quadrature formulae for the optimal control of random PDEs

Fabio Nobile

Springer2025

TopoTome: Topology-informed unsupervised segmentation and analysis of 3D images

bioRxiv2025

Related people (1)

Mario Paolone

Mario Paolone received the M.Sc. (with honors) and the Ph.D. degree in electrical engineering from the University of Bologna, Italy, in 1998 and 2002, respectively. In 2005, he was appointed assistant professor in power systems at the University of Bologna where he was with the Power Systems laboratory until 2011. In 2010, he received the Associate Professor eligibility from the Politecnico di Milano, Italy. Since 2011 he joined the Swiss Federal Institute of Technology, Lausanne, Switzerland, where he is now Full Professor, Chair of the Distributed Electrical Systems laboratory and Head of the Swiss Competence Center for Energy Research (SCCER) FURIES (Future Swiss Electrical infrastructure). He was co-chairperson of the technical programme committees of the 9th edition of the International Conference of Power Systems Transients (IPST 2009) and of the 2016 Power Systems Computation Conference (PSCC 2016). He was chair of the technical programme committee of the 2018 Power Systems Computation Conference (PSCC 2018). In 2013, he was the recipient of the IEEE EMC Society Technical Achievement Award. He was co-author of several papers that received the following awards: best IEEE Transactions on EMC paper award for the year 2017, in 2014 best paper award at the 13th International Conference on Probabilistic Methods Applied to Power Systems, Durham, UK, in 2013 Basil Papadias best paper award at the 2013 IEEE PowerTech, Grenoble, France, in 2008 best paper award at the International Universities Power Engineering Conference (UPEC). He was the founder Editor-in-Chief of the Elsevier journal Sustainable Energy, Grids and Networks and was Associate Editor of the IEEE Transactions on Industrial Informatics. His research interests are in power systems with particular reference to real-time monitoring and operation, power system protections, power systems dynamics and power system transients. Mario Paolone is author or coauthor of over 300 scientific papers published in reviewed journals and international conferences.

Related people (1)

Mario Paolone