This text presents a consolidated survey of the vibrant field of research known as the theory of semi-feasible algorithms. This research stream showcases the richness of, and contrasts between, the central notions of complexity: running time, nonuniform complexity, lowness and NP-hardness.