Suppose you are writing an algorithm for your CS 201 class. You are told that it

Question

Suppose you are writing an algorithm for your CS 201 class. You are told that it has to be both recursive and ridiculous. Here's what you have so far: Algowidm(head) {if head is null return 0 else if head squareroot next is null return 1 else total = 0 temp = head while temp is not null total += Algowidm(head squareroot next) temp = temp squareroot next return total} Assume that when this function is called, it is given the head of a linked list. Let T(n) be the number of operations performed by Algowidm on a linked list with n elements. Write a recurrence relation defining T(n). A complete relation will include T(0), T(1), and the recursive definition of T(n) for all n greaterthanorequalto 2.

Explanation / Answer

The Recurrance relation is


T(0) = 0
T(1) = 1

T(n) = T(n-1) + 1

Explanation as why -

1. Base cases we can infer from the program itself for n=0 and 1
2. We can see we are everytime incrementing by 1 , we move to next element so its head->next,
Everytime we move by one, n decreases by 1

Hence the answer.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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