[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 Assignmentchef 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 loglogn1000logn (logn) 2010nn lognn 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)suchthatc1f(n)d1fornn0 forsomevaluen0 >0. Therearemany
ways this might be implemented.
Oneinterestingsolutionisgivenbyf(n)=1n1 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 clogn logkn dlogn 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 clogn log(k+n) dlogn 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(12345n)=log(n!)Asdiscussedinthe notes, this is (n log n). CS: assignmentchef QQ: 1823890830 Email: [email protected]