Определение временной сложности алгоритма (log n или n)

Question

 int silly(int n, int m) {
 if (n < 1) return m;
 else if (n < 10)
  return silly(n/2, m);
 else
  return silly(n - 2, m);
}

Является ли этот алгоритм O (log n) или O (n) в терминах записи Big-Oh?

Answer 1

Если оптимизатор действительно хорош, это O (1). Код эквивалентен просто return m.

. Принимая его как данность, мы можем исключить условие if( n < 10 ), потому что это n итераций, когда n мало. Мы ищем наихудший случай, когда n большое.

Это просто оставляет повторение в silly(n - 2, m), который отсчитывает все остальные целые числа. Это н / 2 операций. Мы опускаем константу, делая ее O (n).