illustrate the operation of
INSERTION-SORT on the array A =< 30, 41, 59, 26, 41, 20, 68 >. Show intermediate
results for each iteration. What is the running time for INSERTION-SORT with a list
of n integers in Θ notation?
- (5 points) Express the following functions in Θ notation.
3 − 100n
2 + 50n + 600
• nlg(n) + 50n + 20
4+2n + 30n
2 + 100
- (5 points) p37. 2.3-1. What is the running time for a list of n integers in Θ notation?
- (10 points) p39. 2.3-3
Hint: Use k as independent variable instead of n because n is an exact power of 2 and
there is no case with n+ 1 . First, verify the case for k = 1. Then, assume the formula is
true for k and use the hypotheses to prove the formula is true for k+1. Finally, conclude
the formula is true for k.