Question

I have the following code:

//Set.java

import java.util.ArrayList;

public class Set<T> {
    //data fields
    private ArrayList<T> myList;
    // constructors
    Set(){
        myList = new ArrayList<T>();
    }
    // other methods
    public void add(T item){
        if(!membership(item))
            myList.add(item);
    }

    public void remove(T item){
        if(membership(item))
            myList.remove(item);
    }

    public Boolean membership(T item){
        for (T t : myList)
            if (t.equals(item))
                return true;
        return false;
    }

    public String toString(){
        StringBuilder str = new StringBuilder("[ ");

        for(int i = 0; i < myList.size() - 1; i++)
            str.append(myList.get(i).toString()).append(", ");

        if(myList.size() > 0)
            str.append(myList.get(myList.size() - 1).toString());

        str.append(" ]");

        return str.toString();
    }

}

(20 points) Fill the following table with the big-O running times of each of the methods implemented, as well as the running times for the same methods if they were implemented with LinkedList instead. (No need to explain here, only the big-O expression.)

	Array List	Linked List
add
remove
membership
toString

(20 points) Explain each of the eight running times in the table applying the rules of counting seen in class, and for the method calls, if 4 we have covered them already, directly refer to the running times of those methods. (Partial credit if you do not explain all eight. No points for ambiguous explanations. For instance, if you implement add in the class Set using addFirst in the class ArrayList, then you should say something like the following. “The add method of Set is implemented with just one method call to addFirst of ArrayList. addFirst of ArrayList is in O(n) in the worst case. Hence, the same bound on the running time applies to add”. )

Answer 1

	Array List	Linked List
add	O(n)	O(n)
remove	O(n2)	O(n)
membership	O(n)	O(n)
toString	O(n)	O(n)

Explanation:

1) add : For adding an element we need to check if it is present in the ArrayList/Linked List of not, This will take O(n) time and then we can just add that element . Hence for ArrayList/Linked List, this will take O(n) time


2) remove : For removing an element we need to check if it is present in the ArrayList/Linked List of not, This will take O(n) time and then we can just remove that element from arrayList . Hence for ArrayList/Linked List, this will take O(n²) time.
Membership will take n and remove takes n. Hence its n*n = n²

In Linked list we just need to manipulate references, So find the element and then manipulate the references as we dont have to shift all the elements unlike arrayList.

3) Membership : if it is present in the ArrayList/Linked List of not, This will take O(n) time as we need to iterate till the end.
Hence this will be same for arrayList or Linked list


4) toString(): We iterate the list or Linkedlist till the size. Hence for ArrayList/Linked List, this will take O(n) time.

Thanks, PLEASE COMMENT if there is any concern.