Временная сложность вышеуказанной программы составляет O(2 ^ k), где k - глубина рекурсии.Здесь 2 вытекает из того факта, что в каждом рекурсивном вызове мы выполняем вызовы на 2 других рекурсивных вызова.Теперь давайте проанализируем самую глубокую глубину рекурсии (k).
На рисунке выше рекурсивный путь, деленный на 2 на каждом шаге, будетзаймет больше времени, чтобы достичь его значения меньше 1 (что является базовым случаем), и, следовательно, это будет самая глубокая глубина рекурсии.Поскольку каждый раз мы делим n на 2.Для достижения менее чем 1 потребуется выполнить шаги журнала.Хотя мы также делим n на 3.Разделение n на 2 займет больше времени и, следовательно, ответственно как решающий фактор для самой глубокой рекурсии.Для деталей:
При вызове 1st мы уменьшаем n на n / 2.
При вызове 2nd мы уменьшаем n на (n / 2) / 2 =n / 4 = n / 2 ^ 2.
Следовательно, на шаге Kth мы уменьшаем n на: n / 2 ^ k = 1.
Итак, n = 2 ^ k.
Взятие базы 2 с обеих сторон,
log2 n = log2 (2 ^ k)
log2 n = k log2 (2)
log2 n = k * 1 [поскольку log2 (2) равно 1]
Следовательно, при самой глубокой рекурсии нам нужно k = log(n) шагов для достижения n = 1 и еще одногошаг для достижения n <= 0. Но общая глубина рекурсии будет в диапазоне от <code>log3 n до log2 n.
Таким образом, общая сложность времени составляет O(2 ^ log n) в худшем случае.Но, поскольку мы также делим n на 3, и, следовательно, вся глубина рекурсивного пути, начиная с верхнего до конечного узла, не будет такой же, как у log n.Следовательно, мы можем заключить, что сложность времени равна O(2 ^ k), где k - глубина рекурсии.