Как получить Big O временную сложность кода?

Question

Я хорошо понимаю нотацию Big O, но меня очень смущает этот вопрос:

Учитывая отсортированный список с N элементами, и что поиск ключа повторяется R раз всписок, в чем сложность my_search () в терминах нотации O?

def my_search( data, key ):
 found = False
 low = 0
 count = 0
 high=len(data)-1
 while ( not found and low<=high):
     guess = (high+low)//2
     print('guess: ', guess)
     if ( key == data[guess] ):
         found = True
         count = 1
         k = guess - 1
         while k>=0 and data [k] == key:
             count += 1
             k -= 1
         k = guess + 1
         while k < len(data) and data [k] == key:
             count += 1
             k += 1
     else:
         if (key < data[guess]):
             high=guess-1
         else:
             low = guess+1
 print('count:', count)
 return count

Переданные аргументы для этой функции - это список и ключ, функция вычисляет, сколько раз ключпоявится в списке, например my_search([1,1,2,2,3,3,3,3,3,3,6,7], 1).Ключ ответа говорит, что сложность времени для этого кода составляет , как они пришли к этому ответу?

Answer 1

поиск в упорядоченном списке - O (log (N)) ( бинарный поиск ).как только вы нашли искомый элемент, вам нужно проверить (как минимум) R элементов на предмет, который вы искали.итого O (log (N)) + R.