Рекурсивная функция Big-Oh Сложность

Question

Algorithm multiply(n, m)
PRE: n :: Integer, greater than or equal to 0
m :: Integer
POST: ????
RETURNS: the product, n * m
if (n = 0)
return 0
else if (n is even)
return multiply(n/2, m+m)
else
return m + multiply((n-1)/2, m+m)
endif

Является ли эта функция O (logn), потому что она делит n в каждом рекурсивном случае?Я учусь на среднесрочную перспективу, и я хочу убедиться, что я делаю это правильно.Заранее спасибо.

Answer 1

Да, вы правы.

Хотя здесь дело обстоит именно так, будьте осторожны, делитель в рекурсивном вызове не всегда указывает на логарифмическую сложность.