Calculating the Recurrence Relation T(n)=T(n / [(log n)^2]) + Θ(1)

Question

I tried to solve this problem many hours and I think the solution is O(log n/[log (log n)^2]). but I'm not sure.Is this solution correct?

Answer 1

Expand the equation:

T(n) = (T(n/(log^2(n)*log(n/log^2(n))^2) + Theta(1)) Theta(1) = 
        T(n/(log^4(n) + 4 (loglog(n))^2 - 4log(n)loglog(n)) + 2 * Theta(1)

We know n/(log^4(n) + 4 (log(log(n)))^2 - 4log(n)log(log(n)) is greater than n/log^4(n) asymptotically. As you can see, each time n is divided by log^2(n). Hence, we can say if we compute the height of dividing n by log^2(n) up to reaching to 1, it will be a lower bound for T(n).

Hence, the height of the expansion tree will be k such that

n = (log^2(n))^k = lof^2k(n) =>‌ (take a log) 
    log(n) = 2k log(log(n)) => k = log(n)/(2 * log(log(n)))

Therefore, T(n) = Omega(log(n)/log(log(n))).

For the upper bound, as we know that n/(i-th statement) <‌ n/log^i(n) (instead of applying log^2(n), we've applied log(n)), we can say the height of division of n by log(n) will be an upper bound for T(n). Hence, as:

n = log^k(n) => log(n) = k log(log(n)) => k = log(n) / log(log(n))

we can say T(n) = O(log(n) / log(log(n))).