[10] Draw pictures that show the data structure each time a checkpoint is reached for the problems of sizes one, two, three and four specified as integer n_digit is the number of items in the list and this is followed by n_digit integers) 1 9 278 3654 41302 and indicate for each instance, the number of times the marked statement is executed while creating the linked list. (b) [5] A loop invariant is a statement about a loop used to prove properties about a loop. Fill in a correct function for f (k) in the following loop invariant and then prove that your loop invariant is correct by induction.

Loop invariant: At checkpoint #2 of the kth iteration of the while loop, the current pointer will be pointing to cell number f (k) on the linked list where the cells are numbered starting with cell one. (c) [5] Set up a recurrence which counts the number of times that the statement with the comment // Statement to count. is executed for a given value of n and justify your formula. (d) [5] Solve your recurrence from (c) to get a closed formula