Which is false?

Solution:

We need to identify the false asymptotic statement.

1. 100n log n = O((n log n)/100)

This statement is true because Big O notation ignores constant multiplicative factors. Both expressions belong to the same asymptotic complexity class.

1. √log n = O(log log n)

This statement is false. As n becomes very large, √log n grows faster than log log n. Therefore, √log n cannot be bounded above by O(log log n).

1. If 0 < x < y, then n^x = O(n^y)

This statement is true because n^x grows slower than n^y when x < y. Hence, n^x can be bounded above by a constant multiple of n^y.

1. 2^n ≠ O(nk)

This statement is true because exponential functions grow much faster than polynomial functions for any constant k.

Hence, the false statement is:

√log n = O(log log n)