Compute the asymptotic run time and space complexity for all the methods in the following code:

public class MaxHeap {

// Instance variables private Integer[] heap; private int capacity; // Amount of memory allocated private int size; // Num of items stored

/** * Parameterized constructor * * @param initialCapacity * - initial amount of memory allocated */ public MaxHeap(int initialCapacity) { this.capacity = initialCapacity; this.size = 0; this.heap = new Integer[this.capacity]; }

/** * Parameterized constructor * * @param someArray * - Array containing some integers */ public MaxHeap(Integer[] someArray) { this(someArray.length);

// Insert all elements in someArray into heap for (Integer n : someArray) insert(n); }

/** * Inserts value n in this max heap. Duplicates are allowed. If there is no * room for insertion in the current array storing the items, then an array * of double size has to be allocated and all items are copied into the new * array after which insertion is performed. * * @param n * - item to be inserted */ public void insert(int n) { // Check if there is room for insertion if (this.capacity == this.size) { // Double the capacity this.capacity *= 2;

// Create new array with double size Integer[] newArray = new Integer[this.capacity];

// Copy elements from heap array to newArray for (int i = 0; i < this.size; i++) newArray[i] = this.heap[i];

// Point heap to newArray this.heap = newArray; }

// Insert n into heap this.heap[this.size] = new Integer(n);

// Increment size this.size += 1;

// Build max heap buildHeap(); }

/** * Build heap */ private void buildHeap() { for (int i = (this.size - 1) / 2; i >= 0; i--) buildMaxHeap(i); }

/** * Builds max heap */ private void buildMaxHeap(int i) { int left = (2 * i) + 1; int right = (2 * i) + 2;

int max = i; int len = this.size - 1;

// Check if element at left is greater than element at max if ((left <= len) && (this.heap[left] > this.heap[max])) max = left;

// Check if element at right is greater than element at max if ((right <= len) && (this.heap[right] > this.heap[max])) max = right;

if (max != i) { // Swap element at i with element at max Integer temp = new Integer(this.heap[i].intValue()); this.heap[i] = new Integer(this.heap[max].intValue()); this.heap[max] = new Integer(temp.intValue());

// Check the swapped position if it satisfies the max heap process buildMaxHeap(max); } }

/** * Removes the item with the largest value and returns it. * * @return - the item with the largest value */ private int deleteMax() { Integer largestVal = null; if (this.size > 0) { // Get largest value largestVal = this.heap[0];

// Move all elements one position up for (int i = 1; i < this.size; i++) this.heap[i - 1] = new Integer(this.heap[i].intValue());

// Decrement size this.size -= 1; }

// Create max heap buildHeap();

return largestVal; }

/** * Returns a string representing the sequence of integer values stored in * the heap, in order they are stored in the array */ public String toString() { StringBuffer sb = new StringBuffer();

for (Integer n : heap) sb.append(n + " ");

return sb.toString(); }

/** * Applies heap sort algorithm to sort the input array. * * @param arrayToSort * - Array to sort */ public static void heapsort(Integer[] arrayToSort) { // Create MaxHeap object MaxHeap maxHeap = new MaxHeap(arrayToSort);

// Create an array to hold the sorted Integer[] newArray = new Integer[maxHeap.getSize()];

// Delete max element until size of maxHeap is not zero int index = 0; while (maxHeap.getSize() != 0) newArray[index++] = maxHeap.deleteMax();

// Copy items from newArray to arrayToSort for (int i = 0; i < newArray.length; i++) arrayToSort[i] = new Integer(newArray[i].intValue()); }

/** * @return the capacity */ public int getCapacity() { return capacity; }

/** * @return the size */ public int getSize() { return size; }

public static void main(String[] args) { // Create an array of integers Integer[] arrayToSort = new Integer[] { 3, 5, 9, 6, 8, 20, 10, 12, 18, 9 };

// Display original array System.out.print("Original array: "); for (Integer n : arrayToSort) System.out.print(n + " ");

// Create max heap MaxHeap.heapsort(arrayToSort);

// Display sorted array System.out.print(" Sorted array: "); for (Integer n : arrayToSort) System.out.print(n + " "); } }