public class MyArray $\{$

$//$ Assume ints can get arbitrarily large but simple operations

$//$ on them still remain worst case O$(1).$

private int$[]$ a $=$ new int$[0]$;

private int n$,$ m $=-1$;

public void add$($int obj$)\{$

if $($n $==$ a$.$length$)\{$

grow$()$;

$\}$

a$[$n$]=$ obj;

n$++$;

$\}$

private void grow$()\{$

$//$ Assume array allocation takes O$(1)$ time.

int$[]$ temp $=$ new int$[2*($m $+1)+$ a$.$length $+1]$;

m$++$;

for $($int i $=0$; i $<$ n; i$++)\{$

temp$[$i$]=$ a$[$i$]$;

$\}$

a $=$ temp;

$\}$

$\}$

In this problem, you will do an aggregate analysis on the MyArray class under the

assumption that the number of array assignment operations is directly proportional to

the worst case running time of add$()$ and grow$().$

$($a$)(10$ points$)$ What is the worst$-$case running time for one call to add?

Give a tight asymptotic bound.

Justify your answer.

$($b$)(10$ points$)$ Going forward, let T $($N $)$ be the total number of array assignment op$-$

erations in a sequence of N calls to add$()$ on a MyArray.

Use your answer from part $($a$)$ to do an $$overly$-$pessimistic$$ worst$-$case analysis on

T $($N $).$ State your answer using asymptotic notation.

Justify your answer.

$($c$)(10$ points$)$ Use your overly$-$pessimistic asymptotic upper bound on T $($N $)$ from

part $($b$)$ to derive the amortized cost per call to add$()$ on a MyArray. State this

quantity using asymptotic notation.

Justify your answer.

$($d$)(10$ points$)$ Going forward, we will derive a more meaningful upper bound on T $($N $).$

In a sequence of N calls to add$()$ on a MyArray, how many array assignment

operations are executed in JUST add$()$ and not grow$()?$

Justify your answer.

As part of your justification, state a valid summation expression that represents

this quantity and evaluate it but don$$t use asymptotic notation.

$($e$)(10$ points$)$ In a sequence of N calls to add$()$ an a MyArray, at most how many

array assignment operations are executed in JUST grow$()?$

Justify your answer.

As part of your justification, state a valid summation expression that represents the

least upper bound on the number of array assignment operations executed in JUST

grow$().$

You must evaluate $($upper bound$)$ your summation expression but don$$t use asymp$-$

totic notation.

Hint: Assuming k is a positive integer, then the following is true:

kX

i$=1$

i$2=$ k$($k $+1)(2$k $+1)$

$6$

$($f$)(10$ points$)$ Use your conclusions from parts $($d$)$ and $($e$)$ to derive the amortized

cost per call to add$()$ in a sequence of N calls to add$()$ on a MyArray.

State your answer using asymptotic notation.