Время прогона: Bounds vs Case

Примечание: Пожалуйста, не отмечайте это как домашнее задание! Я не студент и это не задание. Я инженер-программист, который убирает пыль с моего старого учебника "Структуры и алгоритмы данных" и пытается вспомнить то, чему я научился много лет назад, и что, кажется, я не могу найти нигде в Интернете.

Я вспоминаю конкретную лекцию, и в моем учебнике усилено, что границы алгоритмов (верхние, узкие и нижние) и кейсы (лучшие, средние и худшие) - не одно и то же. Но всю жизнь я не могу вспомнить, как эти два понятия отличаются друг от друга.

Для меня, если какой-то алгоритм является O(n) наихудшим случаем, то он может выполнять хуже, чем какая-либо линейная функция, например f(n) = cn + k. Так как мы гарантируем это в худшем случае, то мне кажется, что его верхняя граница также линейна.

Я знаю, что ошибаюсь, просто не могу понять, почему.

Я - контекстуальный ученик, так что если бы кто-нибудь мог привести значимый пример, где либо худший случай не является верхней границей, либо лучший случай не является нижней границей, или где средний случай не является жестко привязанным, то это, наверное, дошло бы до меня быстрее всего.

Спасибо за любую ясность!