Why does GATE-style algorithm analysis usually use worst case rather than average case?
Aworst case gives a hard guarantee and is easier to compute than the average
Baverage-case analysis is forbidden under the SQL standard
Cworst-case bounds are always larger than the actual running time, which makes the math easier
Dworst case ignores constants and so is faster to write
Answer & Solution
Correct answer: A. worst case gives a hard guarantee and is easier to compute than the average
The lecture explicitly emphasises the three reasons: hard guarantee, usually easier than averaging over a distribution, matches real-world constraints (deadlines, security). Average-case requires a probability distribution that is often unknown. Worst-case being larger does not make math easier; it gives true upper bounds.
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