Просьба, если в ответе решите использовать высшую математику, переведите сразу на обыденный язык, чтобы все было понятно и не возникло новых вопросов.
O-большое - аналог нестрогого неравенства (≤),
o-малое - аналог строгого неравенства (<).
Пример:
s = 0
for i in range(0, n):
for j in range(0, n):
s += i * j
То, что его сложность равна Cn2 очевидно - внешний цикл делает n повторений. Внутренний цикл - тоже n повторений. Тело внутреннего цикла считается за константу. По правилам комбинирования вложенных циклов перемножаем сложности - получаем Cn2. Но если его сложность равна квадрату, то она и меньше либо равна квадрату. Можем написать сложность алгоритма O(n2).
В случае с o-малым нужно предъявить такую формулу, что сложность алгоритма будет строго меньше этой формулы. Например сложность этого алгоритма есть o(n3) - он работает быстрее чем любой кубический алгоритм. Или o(n2.1), o(n2+ε) для любого ε > 0, или o(n2log(n)), или ещё бесконечное число вариантов из которых нельзя выбрать один "самый подходящий".
Аналогия на числах: есть формула -x2, оцените её максимальное значение.
Простой ответ в терминах O-большого — -x2 ≤ 0. Не превосходит. А в терминах o-малого оценку привести сложнее: -x2 < 1, -x2 < 0.1, -x2 < ε (ε > 0). Если вы предъявляете конкретный ответ со строгим неравенством, сразу можно сказать что ваш ответ не самый лучший - ε можно разделить пополам и получить лучший ответ.
Лучшего ответа нет вообще. Есть последовательность ответов, каждый лучше предыдущего. Поэтому строгое неравенство непрактично использовать при оценках сверху.
Совсем на пальцах
о-малое - это не просто "меньше". Когда пишут, что сложность алгоритма - о(f), то хотят сказать, что с ростом параметра алгоритма сложность растёт гораааааааздо медленнее, чем f. Там, на бесконечности, сложность алгоритма даже в микроскоп не разглядеть по сравнению с f. Ну или как песчинка по сравнению с галактикой. Очень-очень-очень намного-намного-меньше, короче.
О-большое - это не просто "меньше или равно". Это означает, что где-то там, на бесконечности, сложность алгоритма ведёт себя примерно как f. Если совместить масштабы, то может быть даже совпадут. Ну или могут быть выбросы соответствующего размера. В случае о-малого как масштаб ни растягивай, всё равно мелко будет.
С практической точки зрения О-большое полезнее. Предположим, мы знаем, что два алгоритма имеют сложность о-малое от эн-в-кубе, o(n^3). Что это нам даёт? Ничего. А если мы знаем, что у одного сложность O(n^2), а у второго O(n*log(n))? Сразу ясно-понятно, что нужно брать второй.
но как человек, которому в жизни довелось доказывать сложность алгоритма, я думаю, что причина использования О-больших в другом
Тоже на пальцах, но чуть сложнее
Чисто из общих соображений: на ваш вопрос "Почему при оценке сложности алгоритмов используют O-большое?" ответить невозможно, так как он неверен.
При оценке сложности в специальной литературе, то есть не учебниках, используют и О-большое, и о-малое, и даже Омега-большую (Ω), омега-малую (ω) и Тета-большую (Θ). И даже используют знак ~ (тильда). Хуже того, для алгоритмов факторизации помимо О-Омега-Тета-тильда используют ещё и букву L.
Да что там специальная литература! В Википедии местами используют не только О-нотацию. Например, в статье о рекуррентных соотношениях (в английском эта теорема получила уважительное название Master theorem) текст пестрит Тета-нотацией.
И всё же, почему так широко используют О-большое? Чем О-большое удобнее о-малого? Давайте посмотрим на определение О-большого, для простоты взяв случай n ⟶ ∞:
Здесь U - окрестность бесконечности, то есть луч чисел n > N для некоторого N.
Что же написано в определении о-малого?
Видите в чём разница? В первом кванторе. Для О-большого стоит квантор существования, а для о-малого квантор всеобщности. Конечно же первый квантор доказывать гораздо проще: нашел константу C, доказал, что для всех достаточно больших n неравенство выполняется, и свободен! С квантором всеобщности дело гораздо веселее. Нужно доказывать, что |f(n)/g(n)| ⟶ 0, то есть показать что там, на бесконечности, никаких выбросов быть не может. В большинстве случаев это шибко сложно, мало кто хочет с такой фигнёй связываться.
Возьмём для примера теорему о распределении простых чисел 
Чебышов сравнительно элементарными средствами доказал в 1850-м году, что π(x) "болтается вокруг" x/ln(x) и нашел константы, которые ограничивают отклонения. Но тот факт, что эти константы равны единице, и асимптотически π(x) сливается с x/ln(x) доказали только спустя 50 лет, причём это потребовало введения Риманом такой ниипической пушки, как дзета-функция, и аггрессивного развития теории функции комплексной переменной.
ИМХО, причина использования О-большого заключается именно в сложности доказательства теорем для о-малого.