time complexity
Почему
if n <= 1:
return 0
else:
return f(n/2) + 1
по времени O(logN)
а
if n < 10:
return n
else:
n = n % 10
return f(2*n)
по времени O(1)?
Источник: Stack Overflow на русском
Ответы
Ну, в первом случае для ну очень большого n мы получаем примерно последовательность n, n/2, n/4 ... — т.е. порядка log(n) членов.
Во втором случае первый же вызов урезает n до значения, не превышающего 10, а ко второму вызову — 18. И никак больше 3 вызовов не получится — для 9. Т.е. количество вызовов ограничено константой для любого n. O(1).
Так понятнее?