Поймите, что
Для вашего примера это означает, что 
и 
оба удерживают.
Ради интуиции вы можете сделать следующие ассоциации:
Очевидно, 
= y and y <= y <=> x = y">.Отразите это на символизме асимптотических границ, и вы получите первую эквивалентность.
Теперь давайте формально покажем, что не может быть более жесткая верхняя граница, чем .
Предположим, что была более жесткая асимптотическая верхняя граница, чем 
, то есть 
.Однако мы уже знаем из приведенной выше эквивалентности, что 
также имеет место.
, поэтому не существует такой функции, чтобы обе границы выполнялись, что противоречит предположению.
Для случая 
аргумент аналогичен.
Мы заключаем, что и оба асимптотически жесткие.
Обратите внимание, что вы должны различать жесткие границы и просто границы.Для вашего повторения 
также является верхней границей.Это не асимптотически туго, хотя.По этой причине технически нонсенс находить «верхнюю» и нижнюю границы рекурсии.