Computing everything in essentially linear time