Prove or disprove the following claim for all monotonically increasing functions $f(n)$

42 Views Asked by At

Prove or disprove the following claim for all monotonically increasing functions $f(n)$.

$$f(n) = \theta ((f(\sqrt{n}))^2)$$

1

There are 1 best solutions below

0
On BEST ANSWER

The claim is false. Assume f(n) = log n. It provides a contradiction to the claim.