The table is a java ArrayList of ArrayLists. Each row in the table is an inner ArrayList of the outter ArrayList. How to make a method that add a new column within runtime O(rows()+col()-i)?

Currently I've got a bad method:

public void addCol(int j) {

for (int i = 0; i

table.get(i).add(j, null); //this line takes O(cols()-j) time

}

}

This method is bad because it takes O(rows()*(cols()-j)) time, much longer than what's desired.

Random Access Table Hint: For this part, start with the A2Table class provided as a sample solution for Assignment 2 and included in the archive, but notice that the running times for row and column operations have to be symmetric. This means that, if your implementation uses an ArrayList for each row, the addcol(i) operation cannot afford to call add(i, x) for each row since this would table 0( rows() *( cols ()-1 ))) time Note: This isn't just a hack job. There are a couple of tricks to this that you have to figure out before you start coding Hint 1: To make addcol(i) fast enough, you have to avoid calling add(i,nul1) for each row in your table. You can, however, afford to call add (nul1) for each each rovw Hint 2: To make removeCol(i) fast enough, you have to avoid calling remove(i) for each row in your table. You can, however, afford to call set(i,null) for each row Implement the FasterTable class that supports the following operations 1. rows() returns the number of rows in the Table (constant time) 2. cols() returns the number of columns in the Table (constant time) 3. get(i,) return the item at rowi and columnj in the Table (constant time) 4. set(i,j,x) set the item at row and column j to x in the Table and return the value previously stored there (constant time) 5. addRow(i) insert a new row at index i . This creates cols() new entries in the Table, which are all initialized to null. This causes the indices of rows i, ,rows)-1 to increase by 1. (O( cols rows() i)time) 6. removeRow(i) remove row i. This causes the indices of rows+ rows() -1 to decrease by 1. (O( cols( rows() i) time) 7. addcol(i) inserts a new column at index. This creates rows( new entries in the Table, which are all initialized to null . This causes the indices of columns. cols) -1 to increase by 1. (O(rowscolsi) time) 8. removeCol(i) removes column i. This causes the indices of columns 1. cols -1 to decrease by 1. (O rowcols) -i) time)