recurrence - 複雑な繰り返し関係を解決する

Question

以下の再帰関係をどのように解決しますか?

T(n) = 2T(root(n)) + logn/loglogn if n > 4
T(n) = 1 if n <= 4

できればマスター定理によって、それ以外の場合は任意の方法で。マスター定理が失敗することは知っていますが、この種の問題の拡張機能はありますか? 上記のような複雑な関係を解決するための何かを教えてもらえますか?

Answer 1

私はこれがうまくいくはずだと思います：

n = 2^m かつ T(2^m) = s(m) の場合

logn = m、loglogn = logm;

s(m) = 2*s(m/2) + m/logm ;

上記の方程式を解くことが私たちの問題です.これを解くためにマスター定理を使用することはできません.この問題を解決してから、パラメータを再度 n に変更します。

Answer 2

私によると

n = 2^m かつ T(2^m) = s(m) の場合

logn = m、loglogn = logm;

s(m) = 2*s(m/2) + m/logm ;