For each of the following pairs of functions, either f ( n ) f(n) is in O
Question:
For each of the following pairs of functions, either f(n)f(n) is in O(g(n))O(g(n)), \( f(n)) is in Ω (g(n)) Ω(g(n)), or f (n) = Θ (g(n) ) f(n)=Θ(g(n)). For each pair, determine which relationship is correct. Justify your answer, using the method of limits discussed in Section 3.4 .5.
(a) f(n) = log n^2; g(n) = log n + 5.
(b) f(n) = √n; g(n) = log n^2.
(c) f(n) = log n^2; g(n) = log n.
(d) f(n) = n; g(n) = log^2 n.
(e) f(n) = n log n + n; g(n) = log n.
(f) f(n) = log n^2; g(n) = (log n)^2.
(g) f(n) = 10; g(n) = log 10.
(h) f(n) = 2^n; g(n) = 10n^2.
(i) f(n) = 2^n; g(n) = n log n.
(j) f(n) = 2^n; g(n) = 3^n.
(k) f(n) = 2^n; g(n) = n^2.
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Related Book For
Practical Introduction To Data Structures And Algorithm Analysis Java Edition
ISBN: 9780136609117
1st Edition
Authors: Clifford A. Shaffer
Question Posted: