A Machine Learning Approach to Predicting the Smoothed Complexity of Sorting Algorithms

Bichen Shi, Michel Schellekens, Georgiana Ifrim

Smoothed analysis is a framework for analyzing the complexity of an algorithm, acting as a bridge between average and worst-case behaviour. For example, Quicksort and the Simplex a…