Big O question, is f(n) O(g(n)) just need the answers to this table with a brief

Question

Big O question, is f(n) O(g(n))

just need the answers to this table with a brief written explanation for each answer in the table

ds2-2017-Winter 2017 MATH-240-001 Discrete Structures 1-Google Chrome Secure https://mycourses2.mcgill.ca/d2l/le/content/254757/fullscreen/3180533/View ds2-2017 using Latex. (You may draw any figures by hand if you want. A template is on the course webpage. 2. [12 marks]. Order Notation. For each of the following indicate whether f O(g) or not. Briefly justify your answer. 10n log(n) 2n (log (n)) log n 1.1 n log(n)) 0.01 (log (n))10 log n log(n) n/log(n) k-t-1 3. 13 marks Translation Between English and Predicate Calculus. Translate the following into sentences in predicate calculus. You may assume that C 3:13 PM 2/122017

Explanation / Answer

f(n) is O(g(n)) if C and n0, f(n)Cg(n) n>no

1. f(n) = 10n + logn , g(n)= 2n + (logn)3

f(n)Cg(n)

(10n + logn)C(2n + (logn)3)

(10-2C) + logn( 1- C(logn)2) 0 if C>5

2. f(n) =5logn , g(n)= log(n2)

f(n)Cg(n)

5logn Clog(n2)

5logn C2log(n)

(5-2C)logn0 if C< 2.5

3. f(n) =n1.1   g(n)=n(logn)2

f(n)Cg(n)

n1.1 Cn(logn)2

1.1logn logC + 2logn

-0.9logn logC

4.f(n) =n0.01 ,g(n)=(logn)10

f(n)Cg(n)

n0.01C(logn)10

0.01 logn log C+ 10logn

-9.99logn log C

----------------------------------------------------------------------------

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.