Сложность двоичного поиска

Я смотрю онлайн-лекцию в Беркли Uni и остановился на следующем.

Проблема : Предположим, у вас есть коллекция компакт-дисков, уже отсортирован. Вы хотите найти список компакт-дисков, название которых начинается с «Best Of».

Решение : Мы воспользуемся двоичным поиском, чтобы найти первый случай «Best Of», а затем будем печатать до тех пор, пока тайл больше не является «Лучшим из»

Дополнительный вопрос : Определите сложность этого алгоритма.

Верхняя граница : Верхняя граница двоичного поиска - O (log n), поэтому, как только мы нашли затем мы печатаем, скажем, название k. так что это O (logn + k)

Нижняя граница : нижняя граница двоичного поиска - это Omega (1) при условии, что нам повезло, а заголовок записи - средний заголовок. в данном случае это Омега (k)

Вот как я это проанализировал.

Но в лекции лектор использовал лучший и худший случаи. У меня есть два вопроса по этому поводу:

1. Почему нужно использовать лучший и худший случай, не считаются ли большие O и Omega лучшими и худшими случаями, которые может выполнить алгоритм?

2. Его анализ был Худший случай: Theta (logn + k)
   Лучший случай: Theta (k)

   Если я использую концепцию наихудшего случая как относящуюся к данным и не имеющую ничего общего с алгоритмом, то да, его анализ верен. Это потому, что в худшем случае (название компакт-диска в конце или не найдено) тогда Big O и Omega оба являются log n, там это тета (log n + k).

   Если вы не используете «лучший случай» и «худший случай», то как вы анализируете алгоритм? Верен ли мой анализ?