Given an algorithm whose performance is represented by the function: f(n) = n^2l

Question

Given an algorithm whose performance is represented by the function:

f(n) = n^2lg(n^2) + 2n^1

a. Give a brief description of characteristics of a problem where usch performance might arise

b. Find a simple polynomial g(n), so that f(n) = O(g(n)). State your function g(n)

c. Provide the values of witnesses, c and k, that demonstrate f(n) = O(g(n))

d. What are the values for cg(k) and f(k)?

2. Given an algorithm whose performance is represented by the function f(n)n21g(n2)2n1 a. Give a brief description of characteristics of a problem where such performance might arise b. Find a simple polynomial g(n), so that f(n) -O(g(n). State your function g(n). c. Provide the values of witnesses, c and k, that demonstrate f(n)- 0(g(n)). d. What are the values for cg(k) and f(k)?

Explanation / Answer

a.) It might be a possible case that there are three nested for loops, most outer loop and outer loop in running for n times while inner loop is running lg(n^2) times.

b.) g(n) = n^2lg(n^2)

c.) c = 100, k = 10 (say).

d.) f(k) = 100(2) + 20 =220

c*g(k) = 100*100*2= 20000

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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