(i) Best / Worst / Average Case Complexity

• Best case $T_{best}(n)$: minimum time over all inputs of size $n$. Often overly optimistic.
• Worst case $T_{worst}(n)$: maximum time — guarantee that algorithm never exceeds this.
• Average case $T_{avg}(n)$: expected time over distribution (usually uniform) of inputs — needs probabilistic analysis.

(ii) Example: Linear Search for key $x$ in array $A[1..n]$

for i=1..n: if A[i]==x return i
return -1

• Best: $x=A[1]$ → 1 comparison → $\Theta(1)$ → $O(1)$ / $\Omega(1)$.
• Worst: $x
  otin A$or$x=A[n]$→$n$comparisons →$\Theta(n)$.
• Average (uniform, $x$ always present): expected position $(n+1)/2$ → $\Theta(n)$ comparisons; if $x$ absent with probability $p$, average = $p\cdot n + (1-p)(n+1)/2 =\Theta(n)$.

Similarly Binary Search: best $O(1)$, worst/avg $\Theta(\log n)$; Bubble Sort: best $O(n)$ (with early exit), worst/avg $\Theta(n^2)$.

(iii) Why Worst-Case Preferred

1. Guarantee: bounds response time for real-time / safety-critical systems.
2. Simplicity: does not require input distribution knowledge (average case needs distribution).
3. Dominant for many algorithms: average = worst order-wise (e.g., linear search, quicksort worst $O(n^2)$ but average $O(n\log n)$ — here worst still informs; randomized analysis gives expected worst over random choices).
4. Adversarial inputs: worst-case protects against malicious data.
5. Standard in complexity theory: $P$, $NP$ defined via worst-case polytime.

Note: Average-case is important when worst-case is rare (e.g., QuickSort, Hashing expected $O(1)$), but worst-case remains the default metric published.