4.1 Given the following list of integers. 3, 9, 2, 15, -5, 18, 7, 5, 8 EA.6. Sup

Question

4.1 Given the following list of integers.

3, 9, 2, 15, -5, 18, 7, 5, 8

EA.6. Suppose you are given a list that supports only the operations append, remove, and enumerate, as described in the first three rows of Table 4.1. Give an algorithm describing how you would perform each of the following operations in terms of the given operations (a) Empty a list (i.e., remove all the entries) (b) Remove all occurrences of a given item from a list (c) Obtain the size (i.e., the number of entries) of a list d) Search for a given item in the list, returning true or false depending on whether the item is found or not

Explanation / Answer

a) With the help of enumerte function we can traverse element by elemnet
   and we will be calling remove function on each element.The complexity
   will be of O(n) as we need to traverse the list once.

b) With enumerte function we will traverse element by element. We will
   compare the number to be removed with the element and then call remove    function. The comparions will be n. So it is of order O(n)

c)With enumerte function we will traverse element by element. We will be
increasing the counter by 1.At the end of the list we will have the size.
This is also of complexity of O(n)

d) With enumerte function we will traverse element by element. We will
   compare the number to be searached with every element. The comparions will be    n (worst case). So    it is of order O(n)

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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