6. (10 points) For the recursive algorithm on the Algorithm 3: S(k) 1: Input: A

Question

6. (10 points) For the recursive algorithm on the Algorithm 3: S(k) 1: Input: A natural number k 21 right, set up and solve a recurrence relation for the number of times the algorithm's basic 2: Output: The sum 1+ 2+3++ k. operation is executed. You must clearly iden- tify what the basic operation is and use the appropriate notation (o, e, or ?) to identify 5: else the complexity of the algorithm. Is there a 6: return S(k-1) +k better algorithm? Justify your answer 3: if k 1 then 4: return 1 7: end

Explanation / Answer

Basic operation is when k = 1 So, when k=1 it returns 1 Time Complexity T(n) = T(n-1) + 1 = T(n-2) + 1 + 1 ... ... = T(1) + 1 + 1 + ... + 1 = O(n)

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

---

---

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