Amortized Complexity Example: Dynamic $($Extendable$)$ ArrayWe present a reallocation strategy for an array that will ensure total time complexity O$($n$)$ for n successive insert operations, and thus amortized complexity O$(1)$ for one insert.Problem description:Data are sequentially coming to the input, and are inserted intoan array so that the i$-$th element is stored at index i$.$Design an operation DAInsert for inserting an element in the case whereI Ithe total number n of input data items is unknown,and therefore a static array of sufficient size cannot be allocated beforehand. Extension StrategyConsider the following method of array extension:Let m be the capacity of an array P$,$ and let i be the index of the element we are currently inserting.If i $>$ m $($the capacity is exceeded$)$I allocate a new array of size $2$m$,$I copy the stored values of the original P into the first half of thenew array,I deallocate the old array, and call the new array P$,$I store the new inserted element at index m $+1,$ and double thevalue of m$.$At the beginning, we allocate an array of size $1($just to makethe analysis easier$).$ Extendable Array: Insert Algorithm DAInsert$($P$,$x$)(1)$ Let i be the index of the element we are currentlyinserting.$(2)$If im$,$ store P$[$i$]$:$=$x$,$ i:$=$i$+1,$ and stop.$(3)$ If i$>$m then$(4)$ Allocate P of size $2$m and set$(5)$ Copy P to P$.(6)$ Deallocate P and set P :$=$ P$.(7)$ Store P$[$i$]$:$=$x and i:$=$i$+1.$m :$=2$m$.$ ObservationThe time complexity of the algorithm DAInsert applied to an n$-$element array is $($n$)$ in the worst case. Extendable Array: Amortized AnalysisTheoremSuppose that, at the beginning, the array is empty. Then the time complexity of n successive calls of the operation DAInsert is $($n$).$ Thus, the amortized complexity of one call is $(1).$Proof.To insert n elements, we perform constant$-$time insertions, and from time to time extensions of the array.Simple insertion of n elements needs $($n$)$ time.Extending the array by insertion of i$-$th element needs $($i$)$ time.The array is extended only if i is equal to a power of $2.$Therefore, all the extensions need $(20+21+...+2$k $)$ time in total, where $2$k is the greatest power of $2$ smaller than n$.$This geometric series adds up to $2$k$+11<2$n$,$ which gives a time complexity of $($n$)$ in total. Do this task with other strategies: if the capacity m is exceeded$*$ strategy a$)$: allocate a new array of size $(5$ m$).*$ strategy b$)$: allocate a new array of size $($m$+5).*$ Suppose that, at the beginning, the array is empty.Prove that the time complexity of n successive calls of the operation DAInsert with strategy a$)$ is O$($n$).$ Thus, the amortized complexity of one call is O$*(1).*$ BONUS: Prove that the time complexity of n successive calls of the operation DAInsert with strategy b$)$ is greater than $($n$)($and thus, the amortized complexity of one call cannot be $*(1).$