Question

Is it possible to apply master theorem when f(n) = loglogn?

Master Theorem ref: aT(n/b) + f(n)

Answer 1

The master function is

T(n) = aT(n/b) + (n^k * log^p n)

Where a>=0, b>1, k>=0, and p is a real number

If we satisfy all the above variable conditions, then yes, the master's theorem is applicable.

Given Function is f(n) = log log n

log log n is as same as log² n

F(n) = log² n

We can write F(n) as

F(n) = 0*T(n/b) + (n⁰*log² n)

Here a = 0 but b is unknown. So, b can't be 0. The value of b can be anything greater than 0

K = 0 and p = 2

Since b is unknown, it is difficult to apply to the master's theorem.

Therefore, The master's theorem is not applicable.

Please don't forget to give a positive rating to the answer. Your rating motivates experts to help other students also. Thank you :)