Page 40, Exercise 1

1. Show that the following statements are correct:
(a) 5n² − 6n = θ(n²) Sincen ² is the leading exponent this is correct.
(b) n! = O(nⁿ) n! is the leading exponent and its time is a non-deterministic polynomial, so this is correct.
(c) n²+ n log n = θ(n² ) n² is the leading exponent.
(f) n²ⁿ + 6 . 2ⁿ = θ(n²ⁿ) n²ⁿ is the leading exponent.
(g) n² + 10³n² = θ(n³) Since 10³ is a constant and the time is based on the leading exponent for the variable, this should be n².
(h) 6n³ / (log _n + 1) = O(n³) n³ is the leading exponent.
(i) n^1.001 + n log _n = θ(n^1.001 ) This is debatable because n log_n actually grows at a faster rate than n raised to 1.0001 except for n < 2.
(j) n^k + n + n^klog _n = θ(n^klog_n) for all k ≥ 1. n^klog_n grows at a faster rate.
(k) 10n³ + 15n⁴ +100n²²ⁿ = O(n²²ⁿ) n²²ⁿis the leading exponent.