Задача: Дан большой массив чисел. (~10^7). Найти минимальные k чисел при k=5, k=100 и k=10000.

Решение:

A[10^7] - массив размера N, в котором происходит поиск.
0. i = k+1;
1. while (i < N) {
2.   Находим i_max = индекс для max(A[1]...A[k]);
3.   if (A[i] < A[i_max])
4.        меняем местами A[i] и A[i_max];
5.    i++;
6. }
A[1]...A[k] - содержит k минимальных элемента массива

Комментарии:
Сложность этого алгоритма O(N)+O(N*k)
O(N) - Это планомерный проход по массиву.
O(N*k) - Это максимум N раз искать максимальный из первых k элементов. Это может быть только в случае обратно отстортированного массива. В случае прямо отсортированного массива, сложность равна O(N).
На строке 2. находим максимальный элемент из первых k элементов.
Если на строке 3. выясняется, что мы нашли элемент меньше, чем максимальный в нашем подмассиве, то мы теперь заинтересованы иметь новый найденный элемент, поэтому на строке 4. меняем местами эти два элемента. Продолжаем идти по массиву и искать элементы меньше, чем максимальный из нашего подмассива.