[SOLVED] 留学生考试辅导 Theoretical Computer Science (M21276)

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代写加微信 assignmentchef

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代考加微信: assignmentchef QQ: 1823890830 Email: [email protected]