complexity-theory Definition Worst-Case Complexity Worst-case complexity is the greatest possible runtime of a program for a given input size n.