Assignment 2

Running Time and Memory Usage for Make Unique Function

public void makeUnique() {
	DynamicArray<T> existing = new DynamicArray<T>();
	
	for (DLLNode<T> value : this) {
		if (!existing.contains(value.data))
			existing.append(value.data);
		else
			deleteNode(value);
	}
}

---

Running Time

The above algorithm consists of two parts:

Part	Purpose	Runtime Cost
A	[[Assignment 2#A Allocation of a new DynamicArray type|Allocation of a new DynamicArray type]]	$T_A(N)$
B	[[Assignment 2#B Iterating through the DoublyLinkedList|Iterating through the DoublyLinkedList]]	$T_B(N)$

Since these parts are sequential, we can find the overall runtime cost $T_N$ as: $T_N=T_A(N)+T_B(N)$

A: Allocation of a new DynamicArray type

As per it’s constructor:

public DynamicArray() {
	this.storage = (T[]) new Object[capacity];
}

It is clear that all it is responsible for is initialisation, hence, $T_A(N)=\Theta (1)$

B: Iterating through the DoublyLinkedList

As per the Iterable implementation on DoublyLinkedList:

@Override
public Iterator<DLLNode<T>> iterator() {
	return new Iterator<DLLNode<T>>() {
		/**
		 * The current node indexed by the iterator
		 */
		private DLLNode<T> current = head;
		
		/**
		 * @return if the next node in the list exists or not
		 */
		@Override
		public boolean hasNext() {
			return current != null;
		}
		
		/**
		 * @return the next node in the list
		 */
		@Override
		public DLLNode<T> next() {
			DLLNode<T> previous = current;
			current = current.next;
			return previous;
		}
	};
}

In the worse case the below loop is $\Theta (N)$ time, as it makes use of the above Iterator

for (DLLNode<T> value : this)

And in the worst case the contains check is also $\Theta (N)$ as there would be $N$ elements in the DynamicArray

if (!existing.contains(value.data))

public boolean contains(T value) {
	for (T existsInArray : this)
		if (value == existsInArray)
			return true;
		    
	return false;
}

@Override
public Iterator<T> iterator() {
	return new Iterator<T>() {
		int index = 0;
		
		/**
		* @return if the iterator can continue
		*/
		@Override
		public boolean hasNext() {
			return index < length;
		}
		      
		/**
		* @return the next value in storage
		*/
		@Override
		public T next() {
			return storage[index++];
		}
	};
 }

Hence, since the loop calls contains $N$ times in the worst case $N\ast N=\Theta (N^2)$ average time complexity for the loop.

Both DoublyLinkedList#deleteNode and DynamicArray#append can be considered to be constant time operations.

In conclusion by worst case asymptotic analysis, the makeUnique function runs in $\Theta (N^2)$

---

Memory Usage

The algorithm uses the following memory:

Memory User	$\Theta (N)$	Justification
Doubly Linked List	$\Theta (1)$	The list itself is not copied or cloned and is modified in place
Dynamic Array	$\Theta (N)$	The dynamic array may, in the worst case, contain all $N$ elements in the linked list, if every element is unique. Hence it could run with $\Theta (N)$ complexity in the worst case

$M_{cw}=\Theta (N)$