[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)
Answer: True, it is enough to take e.g. c = 2022 and n0 = 2021 b) 108n + 1030 = O(n)
Answer: True, it is enough to take c = 109 and n0 = 1030 c) n3 + 17n2 + 2019 = O(n2)
Answer: False
d) 5n5 + 10n4 = O(n7)
Answer: True, c = 16, n0 = 1. e) 5n5 + 10n4 = Ω(n7)
Answer: False
f) 1000 · 2n + 3n2 = O(n3)
Answer: False
g) 1000 · 2n + 3n2 = Ω(n3)
Answer: True
h) 1000 · 2n + 3n2 = Θ(n3)
Answer: False
i) 20n5 + 7n4 + 8n3 + 108 = Θ(n4)
Answer: False
j) n6 − 108n4 + 8n3 − 108 = Θ(n6)
Answer: True k)10nlogn+n2 =Θ(n2)
Answer: True
l) log n8 + 10 = Θ(n)
Answer: False
Question 2. Order the following functions from N → R in terms of their growth rate
from the slowest to fastest:
, n3 log n, , 1030, (log n)18, log log n, n5, nn 109
, 1000 log n10, n!−1089, n19

30 101835n8
10 ≺loglogn≺1000logn ≺(logn) ≺2010n≺n logn≺n ≺ 12 ≺
≺n19 · 108 ≺ 109 ≺n!−1089 ≺nn
a) List all of the functions that are in O(n4).
Answer: 2010n, 1000 log n10, n3 log n, 1030, (log n)18, log log n
b) List all of the functions that are in Ω(n).
Answer: 2010n, n8 , n!−1089, n19logn, n3 logn, 2n , n5,nn
12 108 109 c) List all of the functions that are in Θ(n3).
Answer: No.
Question 3. Find an example of an increasing function f such that f(n) ∈ Θ(1).
Answer: f is an increasing function if f(a) ≥ f(b) whenever a > b. We also need to find
f(n)suchthatc·1≤f(n)≤d·1forn≥n0 forsomevaluen0 >0. Therearemany
ways this might be implemented.
Oneinterestingsolutionisgivenbyf(n)=1−n1 sinceitincreasesfrom0to1asntends
to infinity. It satisfies the relationship above if c = 0.5, d = 1 and n ≥ 2. Alternatively,
we could replace 1/n with any function which approaches 0 as n gets larger. (E.g. etc.)
Question 4. For any constant k > 1, prove each of the following statements: a)log(kn) = Θ(log n)
b) log(k + n) = Θ(log n)
Answer: a) We need to show that c·logn ≤ logkn ≤ d·logn for all n ≥ n0. We use the relation that log ab = log a + log b and we need to find the numbers c, d and n0. Wecanchoosec=1sincelogk>0ifk>1. Also,wecanchoosed=2forn>k,since in this case, kn < n2 , which implieslogkn < logn2 = 2logn.b) Again, we need to prove c·logn ≤ log(k+n) ≤ d·logn for all n ≥ n0. We choose c = 1, as log n ≤ log(k + n) a because logarithm is an increasing function. As above, we can take d = 2 as long as n is larger than both 2 and k. Under this condition, k+n < n2.Question 5. Can you tell something about the growth of the functions: a) f (n) = 1 + log 2 + log 4 + · · · + log 2nAnswer: We notice that the arguments are all powers of two. Thus, f (n) = 1 + (1 + 2 + · · · + n) log 2 = 1 + n(n+1) log 2. This is of order n2.b) f (n) = log 1 + log 2 + log 3 + · · · + log nAnswer: Wecanshowthatf(n)=log(1·2·3·4·5···n)=log(n!)Asdiscussedinthe notes, this is Θ(n log n).程序代写 CS代考加微信: assignmentchef QQ: 1823890830 Email: [email protected]