The meaning of 'worst case'

Question

When giving bound on convergence rate, complexity and so on, people sometimes will specify it by 'worst case'. What is the meaning of 'worst case'?

Answer 1

As @SBareS mentioned in the comments the worst case analysis is looking at literally that. For algorithm complexity an algorithm may on average run at a different asymptotic rate compared to artificial input which is designed to require more steps or if randomization is involved a run of the algorithm could randomly choose the worst choice every step which may result in a difference in asymptotic growth in run time. For example (again credit to @SBareS) Quicksort where the pivot is chosen uniformly at randomly on average requires $O(nlogn)$ operations. However in the worst case the pivot could partition the elements into a partition of size $1$ and a partition of size $n-1$ for every call leading to a recursion depth of $O(n)$ and each layer requiring $O(n)$ operations resulting in $O(n^2)$ operations