Это рекуррентное отношение O (бесконечность)?

Пусть n = 7^m. Повторение становится

T(7^m) = 49 T(7^(m-1)) + 7^m,

or

S(m) = 49 S(m-1) + 7^m.

Однородная часть дает

 S(m) = C 49^m

и общее решение

S(m) = C 49^m - 7^m / 6

i.e.

T(n) = C n² - n / 6 = (T(1) + 1 / 6) n² - n / 6.

Если вы попробуете метод рекурсии:

T(n) = 7^2 T(n/7) + n = 7^2 [7^2 T(n/v^2) + n/7] + n = 7^4 T(n/7^2) + 7n + n

= ... = 7^(2i) * T(n/7^i) + n * [7^0 + 7^1 + 7^2 + ... + 7^(i-1)]

Когда i растет, n/7^i приближается к 1, и, как упоминалось в другом ответе, T (1) является константой. Итак, если мы предположим T(1) = 1, то:

• T(n/7^i) = 1
• n/7^i = 1 => i = log_7 (n)

So

T (n) = 7 ^ (2 * log_7 (n)) * T (1) + n * [7 ^ 0 + 7 ^ 1 + 7 ^ 2 + ... + 7 ^ (log_7 (n) -1) ]

=> T(n) = n^2 + n * [1+7+7^2+...+(n-1)] = n^2 + c*n = тета(n^2)

Обычно, когда для рекуррентного отношения не указан базовый случай, предполагается, что базовым случаем является что-то T(1) = 1 или что-то в этом роде. Таким образом, рекурсия в конечном итоге завершается.

Есть над чем подумать: вы можете получить бесконечный ряд из вашего дерева рекурсии только в том случае, если дерево рекурсии бесконечно глубоко. Хотя в задаче не был указан базовый случай, вы можете действовать, исходя из предположения, что он есть и что рекурсия останавливается, когда входные данные становятся достаточно малыми для некоторого определения «достаточно малого». Исходя из этого, в какой момент рекурсия останавливается? Оттуда вы сможете преобразовать свой бесконечный ряд в ряд конечной длины, который затем даст вам ответ.

Надеюсь это поможет!