Which of the following is false?

1. Detailed Solution

Let's evaluate each asymptotic Big-O statement to see which one is mathematically incorrect:

• Statement a: 100n log n = O((n log n) / 100) In asymptotic analysis, we ignore constant coefficients.

  • The left side simplifies to: O(n log n)

  • The right side simplifies to: O(n log n) Since both functions grow at the exact same linearithmic rate, it is true that 100n log n = O((n log n) / 100).

  • Status: True

• Statement b: sqrt(log n) = O(log log n)
  Let's compare the growth rates of these two functions by substituting a value like n = 2100:

  • Left side: sqrt(log(2100)) = sqrt(100) = 10

  • Right side: log(log(2100)) = log(100) approx 6.64 As n approaches infinity, a square root function always grows faster than a logarithmic function. To look at it generally, if we let u = log n, we are comparing sqrt(u) against log(u). Since sqrt(u) grows faster than log(u), sqrt(log n) cannot be bounded from above by log log n. Therefore, sqrt(log n) is actually omega(log log n), not Big-O.

  • Status: FALSE

• Statement c: If 0 < x < y then nx = O(ny)
  Since x is strictly less than y, the polynomial function n^y has a higher exponent and will grow strictly faster than nx as n approaches infinity. Thus, nx is asymptotically smaller than or equal to ny.

  • Status: True

• Statement d: 2n ≠ O(nk) (Note: assuming k is a constant exponent)
  An exponential function like 2^n grows strictly faster than any polynomial function nk, no matter how large the constant power k is. Because a polynomial function can never act as an upper bound for an exponential function at infinity, 2n is indeed NOT O(nk).

  • Status: True