Theoretical Computer Science (M21276)
Part B/6: Asymptotic growth
(Jan 4-9, 2022)
Question 1. Decide whether each of the statement is ‘true’ or ‘false’. Give an explana- tion.
Copyright By PowCoder代写 加微信 powcoder
a) 2021n + 2021 = O(n)
b) 108n + 1030 = O(n)
c) n3 + 17n2 + 2019 = O(n2)
d) 5n5 + 10n4 = O(n7)
e) 5n5 + 10n4 = Ω(n7)
f) 1000 · 2n + 3n2 = O(n3)
g) 1000 · 2n + 3n2 = Ω(n3)
h) 1000 · 2n + 3n2 = Θ(n3)
i) 20n5 + 7n4 + 8n3 + 108 = Θ(n4) j) n6 − 108n4 + 8n3 − 108 = Θ(n6) k)10nlogn+n2 =Θ(n2)
l) log n8 + 10 = Θ(n)
Question 2. Order the following functions from N → R in terms of their growth rate from the slowest to fastest:
, 1000 log n10, n!−1089, n19 , n3 log n, , 1030, (log n)18, log log n, n5, nn
of the functions that are in O(n4). of the functions that are in Ω(n).
of the functions that are in Θ(n3).
Question 3. Find an example of an increasing function f such that f(n) ∈ Θ(1).
Question 4. For any constant k > 1, prove each of the following statements: a)log(kn) = Θ(log n)
b) log(k + n) = Θ(log n)
Question 5. Can you tell something about the growth of the functions: a) f (n) = 1 + log 2 + log 4 + · · · + log 2n
b) f (n) = log 1 + log 2 + log 3 + · · · + log n
a) List all b) List all c) List all
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com