## Amortized analysis

### 10/28/21

### Administrivia

### • Read Section 17.3 for tomorrow (10/29)

### Where we left off: Subset sum

### Given a set of n (positive) values v _{1} , v _{2} , ..., v _{n} , is there a subset of them summing to S?

### • T[i][j] = whether can make i using v _{1} , v _{2} , ..., v _{j}

### • T[0][j] = true for all j

### • T[i][0] = false for i ≠ 0

### • T[i][j] = T[i][j-1] || T[i-v

_{j}

### ][j-1]

### Recall: Adding to an ArrayList

**Doubling the array** void add(T value) {

### if(num == vals.length) {

### T[] temp = (T[]) new Object[num*2];

### for(int i=0; i<num; i++) temp[i] = vals[i];

### vals = temp;

### }

### vals[num] = value;

### num++;

### }

**Growing the array by 1** void add(T value) {

### if(num == vals.length) {

### T[] temp = (T[]) new Object[num+1];

### for(int i=0; i<num; i++) temp[i] = vals[i];

### vals = temp;

### }

### vals[num] = value;

### num++;

### }

### Recall: Adding to an ArrayList

**Doubling the array** void add(T value) {

### if(num == vals.length) {

### T[] temp = (T[]) new Object[num*2];

### for(int i=0; i<num; i++) temp[i] = vals[i];

### vals = temp;

### }

### vals[num] = value;

### num++;

### }

**Growing the array by 1** void add(T value) {

### if(num == vals.length) {

### T[] temp = (T[]) new Object[num+1];

### for(int i=0; i<num; i++) temp[i] = vals[i];

### vals = temp;

### }

### vals[num] = value;

### num++;

### }

### What are the worst-case running times of these methods?

### A. O(1) and O(1) B. O(1) and O(n) C. O(n) and O(1)

### D. O(n) and O(n) E. None of the above

### Recall: Adding to an ArrayList

**Doubling the array** void add(T value) {

### if(num == vals.length) {

### T[] temp = (T[]) new Object[num*2];

### for(int i=0; i<num; i++) temp[i] = vals[i];

### vals = temp;

### }

### vals[num] = value;

### num++;

### }

**Growing the array by 1** void add(T value) {

### if(num == vals.length) {

### T[] temp = (T[]) new Object[num+1];

### for(int i=0; i<num; i++) temp[i] = vals[i];

### vals = temp;

### }

### vals[num] = value;

### num++;

### }

### What are the worst-case running times of these methods?

### A. O(1) and O(1) B. O(1) and O(n) C. O(n) and O(1)

### D. O(n) and O(n) E. None of the above

### Both have O(n) worst case time per operation, but…

### • Times (in sec) for adding chars one at a time to a list of chars:

**Final length** **doubling** **incrementing**