Лучший случай/худшие случаи повторения отношений

Question

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

Код:

function max-element(A) 
    if n = 1 
     return A[1] 
    val = max-element(A[2...n] 
    if A[1] > val 
     return A[1] 
    else 
     return val 

Лучший случай Рецидив:

T(1) = 1 
T(n) = T(n-1) + 1 
T(n-1) = T(n-2) + 1 

T(n) = T((n-2) + 1) + 1 
T(n) = T(n-1) + 1 -> T(n) = T(n-k) + k 
Let k = n-1 
T(n) = T(n-(n-1)) + n - 1 
T(n) = T(1) + n -1 
T(n) = 1 + n - 1 
T(n) = n 

Answer 1

Время работы зависит только от количества элементов массива; в частности, это независимо от содержимого массива. Таким образом, наилучшее и наихудшее время работы совпадают.

Более правильный способ моделирования временной сложности состоит в повторении T(n) = T(n-1) + O(1) и T(1)=O(1), поскольку O(1) говорит, что вы тратите некоторое дополнительное постоянное время на каждый рекурсивный вызов. Он четко решает до T(n)=O(n), как вы уже отметили. На самом деле это жестко, то есть T(n)=Theta(n).