Сложность алгоритмов приведите два примера когда алгоритм квадратичной сложности О (n) будет ХУДШИМ выбором чем O(n^2)

С точки зрения голой теории такого быть не может. Чисто практически же, если более сложный алгоритм в итоге потребляет меньше ресурсов (например, памяти), он может быть предпочтительнее простого.

Да, на небольших наборах данных нередко выигрывает интуитивно понятный алгоритм с большим O. "Быстрые" алгоритмы требуют меньше итераций, но чаще всего каждая итерация "быстрого" алгоритма вычислительно сложнее (и потому медленнее), чем "интуитивного". Плюс многие "быстрые" алгоритмы требуют дополнительных вычислений на стадии инициализации.

Потому выигрыш в скорости для "быстрых" алгоритмов начинается только на достаточно больших наборах данных.

Сравнение O(n) и O(n ** 2) не приведу (не приходит в голову задача, имеющая такие варианты), но отсортировать 5 элементов проще и быстрее пузырьком O(n ** 2), чем пирамидой O(n * log(n)).

Чаще всего сортировка нужна лишь для визуального представления. Например, непрерывно сортировать входящие данные (список файлов), которые обновляются множество раз в секунду. При этом, конечный объём буфера заранее не известен и может оказаться довольно большим. Для такой "ненастоящей" сортировки вполне подойдёт даже пузырёк.
UPD.: Кстати, сортировать можно массив указателей, а не сами данные. Так что, накладные расходы на перемещение будут минимальны.

О-нотация не учитывает постоянных коэффициентов.
Алгоритм со сложностью 0.01n^2 будет лучше алгоритма со сложностью 100n при n меньше 10000
Примеры лень придумывать

Всё очень просто - чем алгоритм потребляет меньше памяти - тем он и лучше и не нужно искать кошку в тёмной комнате :) Массу примеров по этой теме вы можете найти на http://example100.com сам когда изучал всё это дело туда постоянно заглядывал для сравнения.