Worst-case running time of an algorithm on input size n is
Athe average running time across all inputs of size n
Bthe running time on the smallest valid input
Cthe maximum running time over all inputs of size n
Dthe running time when the input is already sorted
Answer & Solution
Correct answer: C. the maximum running time over all inputs of size n
Worst case is the maximum over all inputs of size n. It is the true upper bound: on ANY valid input the algorithm runs no slower than this. Average needs a probability distribution; smallest input is unrelated; already-sorted is a specific best/worst case for some algorithms (best for insertion sort, worst for quicksort with naive pivot).
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for