[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)
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]