Sub-Linear Time Algorithms: Fast, Cheap and (Only a Little) Out of Control