Одинакова ли сложность следующих двух повторений?

Question

У меня есть два рекуррентных отношения как:

T(n) = T(n/2) + c       // complexity O(logn)

T(n) = 2T(n/2) + c      // is the complexity O(logn)????

с является константой в обоих случаях, т. е. мы выполняем постоянную работу в части повторения слияния.

Первое повторение - бинарный поиск, где мы постоянно отбрасываем половину массива.

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

В первом случае мы не пересекаем весь массив. Во втором мы пересекаем целое. Теперь, если я построю дерево рекурсии для обоих, я получу сложность O(logn), так как высота обоих деревьев одинакова. Если я ошибаюсь, поправьте меня. Это путаница в моей голове, поэтому, пожалуйста, помогите мне разобраться.

Answer 1

Это не та же сложность. Второй будет что-то вроде O(n)

Простой способ увидеть это исправить c = 0 а также T(1) = a (Whare a является константой).

Затем:

T(2) = 2T(1) = 2a
T(4) = 2T(2) = 4a
T(8) = 2T(4) = 8a
...
T(n) = n*a

Вы можете увидеть линейную сложность.