That's worst case. It means the most adversarial graph imaginable gets a time twice as long as the shortest possible.