Computer Science algorithm problems. Sry that’s a lot small questions. It is ok

Question

Computer Science algorithm problems. Sry that’s a lot small questions. It is ok to be not detailed I will give upvote (20 points) Linked lists (a) Write an algorithm to find the maximum value in a linked list. (b) Provide the O, , and bounds on finding the maximum value in a linked list. (c) Are the O, , and bounds the same for finding the maximum value in a linked list and searching a linked list? Why or why not? (d) Write a proof by contradiction to explain your answer to part c. (e) Write an inductive proof for correctness for searching a linked list. (f) Write a loop invariant proof for the same problem as part e.

Explanation / Answer

Answering first 4 part as per chegg policy

a) Max element:

save first element as max

traverse list element by element (element->next) and compare with current max

if current max is less than element then update curret max with element

return max

b)

To find max we had to traverse full list (all elements need to be compared)

hence all three bounds is n

c) Searching an element is same as finding max as searching also needs to check all element of list

d) Contradiction

Lets see searching element is different from finding max

And then if we search for any element it would check all element can search max as well and hence search and find max will have same complexity.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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