True/False

Question

(logn)^1/2=O(loglogn)

Answer 1

(logn)^1/2  = O(loglogn) => (log)^1/2  ≤ loglogn

Taking log both side

1/2 loglogn  ≤ logloglogn   ==> FALSE  since loglogn > logloglogn .

Hence loglogn ≤ (logn)^1/2  => loglogn = O(√logn)

Answer 2

Substitute logn = t .

equation becomes t^(1/2) = O(logt).

clearly a polynomial term cannot be upper bounded by a logarithmic term.

FALSE

Answer 3

f(n) = √(logn)  &  g(n) = log(logn)

let n = 2^{2^10} 

f(n) = √(log2^{2^10}) = √2¹⁰ = 2⁵

g(n) = log(log2^{2^10}) = log(2¹⁰) = 10

Thus, g(n) < f(n) so (loglogn) = O(logn)^1/2 

Thus, (logn)^1/2=O(loglogn) is FALSE