can you go over how to analyze an algorithm without master theorem. if you want you can show master theorem way however id like you to explain it this way in the picture before master theorem. im not quite sure what n-1, summation are. i do know ci is a constant.

INSERTION-SORT(A) 1 for j - 2 to A. length 2 key - All 3 / Insert A[/) into the sorted sequence All 7-11 4 = -1 5 while i >0 and Ali > hey Ali + 1] = AD -1 A[i+1] = key The running time of the algorithm is the sum of running times for each state- ment executed; a statement that takes a steps to execute and executest times will contribute in to the total running time." To compute 7(n), the running time of INSERTION-SORT on an input of values, we sum the products of the cost and times columns, obtaining T(n) = m + cz(n-1)+can-1) + c - 1) + cs(n-1). Even for inputs of a given size, an algorithm's running time may depend on which input of that size is given. For example, in INSERTION-SORT, the best case occurs if the array is already sorted. For each j = 2.3...... we then find that A[i] = key in line 5 when i has its initial value of j - 1. Thus t = 1 for j = 2.3....., and the best-case running time is T(m) - 4 +ez(n-1)+con-1) + cson-1) + (-1) = (a + ctcates + - + + + c). We can express this running time as an + b for constants and b that depend on the statement costs : it is thus a linear function of If the array is in reverse sorted order--that is, in decreasing order---the worst case results. We must compare each element All with each element in the entire sorted subarray All - 1), and so t; = for= 2.3...... Noting that