Big-O notation. (a) Suppose n is the input size, we have the following commonly seen functions in complexity analysis: f1(n) = 1, f2(n) = log n, f3(n) = n, f4(n) = n log n, f5(n) = n2, f6(n) = 2n, f7(n) = n!, f8(n) = nn. Intuitively, the growth rate of the functions satisfy 1 < log n < n < n log n < n2 < 2n < n! < nn. Prove this is true. [Hint: You are expected to prove the following asymptotics by using the definition of big-O notation: 1 = O(log n), log n = O(n), n = O(n log n), n log n = O(n2), n2 = O(2n), 2n = O(n!), n! = O(nn). (b) Let f, g : N → R+, prove that O(f(n) + g(n)) = O(max{f(n), g(n)}). [Hint: The key is max{f(n), g(n)} ≤ f(n) + g(n) ≤ 2 · max{f(n), g(n)}. Note: Proving this will help you to understand why we can leave out the insignificant parts in big-O notation and only keep the dominate part, e.g., O(n2+n log n+n) = O(n2).]
Big-O notation.
(a) Suppose n is the input size, we have the following commonly seen functions in complexity analysis: f1(n) = 1, f2(n) = log n, f3(n) = n, f4(n) = n log n, f5(n) = n2, f6(n) = 2n, f7(n) = n!, f8(n) = nn. Intuitively, the growth rate of the functions satisfy 1 < log n < n < n log n < n2 < 2n < n! < nn. Prove this is true.
[Hint: You are expected to prove the following asymptotics by using the definition of big-O notation: 1 = O(log n), log n = O(n), n = O(n log n), n log n = O(n2), n2 = O(2n), 2n = O(n!), n! = O(nn).
(b) Let f, g : N → R+, prove that O(f(n) + g(n)) = O(max{f(n), g(n)}).
[Hint: The key is max{f(n), g(n)} ≤ f(n) + g(n) ≤ 2 · max{f(n), g(n)}. Note: Proving this will help you to understand why we can leave out the insignificant parts in big-O notation and only keep the dominate part, e.g., O(n2+n log n+n) = O(n2).]
(c) Let f, g : N → R+, prove that Ω(f(n) + g(n)) = Ω(max{f(n), g(n)}).
[Note: Proving this will help you understand that we can also leave out the insignificant parts in big-Ω notation and the result is still a lower bound, e.g., Ω(n2 + n log n + n) = Ω(n2).]
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 3 images
