Homework #2 Complexity Analysis (100 Points) 1. Explain the meaning of the follo

Question

Homework #2 Complexity Analysis (100 Points) 1. Explain the meaning of the following expressions: 15 points) (a) f(n) is o(na) (b) f(n) is nin c) f (n) is e n 0. 2. Discuss the time complexity of the following algorith 10 points) for (i 5 i na i sum ali-51 for (j i-4 j i; j++) Sum 3. Prove that iz is on'). (10 points) 4. Consider the following two different algorithmsto raise an integer x to a power of n: (40 points) long pow2 (long x int n) long powi (long x, int n) if n 0 if n 0 return 1; return 1; if n 1 return 2: result- 1; if is ven (n) for (i 0; i

Explanation / Answer

1)

(a)       The function f(n) is bounded from ABOVE by O(n2), or more precisely, there exists
       positive numbers c, m such that f(n) (c*n2) for all n m.
      
(b)       The function f(n) is bounded from BELOW by (n2), or more precisely, there exists
       positive numbers c, m such that f(n) (c*n2) for all n m.
      
(c)       The function f(n) is bounded from above and below by a (n2). To
       establish this formally we say that f(n) is O(n2) and f(n) is (n2).
       for all n m, and constants c1 and c2, (c1*n2) f(n) (c2*n2)
      
(2)

The time complexity is O(n).

The outer loop runs from 5 to n, in steps of 1.
The inner loop always runs for constant number of loops. i.e. from i-4 to i, which is 5 times.
Hence the inner for loop contribution to time complexity is constant.

All other statements take O(1) time.

Therefore, the total time complexity is O(n).

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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