Как решить это рекуррентное соотношение: T (n) = 4 * T (sqrt (n)) + n
Я знаю, как решить рекуррентные отношения с помощью Master Method. Также я'Я знаю, как решить повторения ниже:
T (n) = sqrt (n) * T (sqrt (n)) + n
T (n) = 2 * T (sqrt (n)) + lg (n)
В приведенных выше двух рекурсиях на каждом уровне дерева рекурсии выполняется одинаковый объем работы. И есть всего log log n уровней в дереве рекурсии.
У меня возникли проблемы в решении этого: T (n) = 4 * T (sqrt (n)) + n
РЕДАКТИРОВАТЬ: Здесь n - степень 2