Amortized asymptotic bounds

For each of the following lazy data structures, provide the tightest asymptotic bounds you can on the amortized cost of an operation, starting with an empty data structure. Please make sure to provide a clear and terse explanation of your analysis. 2a. Lazy-Queue [9 points] Lazy-Queue maintains an initially empty ArrayList L of integers, an initially unmarked flag, and the following operations: INSERT(X) Add x to the end of L. Mark the flag. EXTRACT-MAX() If the flag is marked, bubble-sort L and unmark the flag. Remove the last integer from L. 2b. Lazy-Set [8 points] Lazy-Set maintains an initially empty vector v of integers and the following operations: INSERT(X) Add x to the end of v. FIND(x) Perform a linear search of v for x. If x is found, PARTITION v on pivot x and return true; else return false. 2c. Lazy-Array [8 points] Lazy-Array maintains two initially empty ArrayList S: UNSORTED and SORTED. INSERT(X) Adds x to the back of UNSORTED. FIND(x) Does a binary search for x in SORTED; if that fails, does a linear search for x in UNSORTED. In either case, if UNSORTED is not empty, then its elements are inserted, one by one, into the SORTED array, as in insertion sort. For each of the following lazy data structures, provide the tightest asymptotic bounds you can on the amortized cost of an operation, starting with an empty data structure. Please make sure to provide a clear and terse explanation of your analysis. 2a. Lazy-Queue [9 points] Lazy-Queue maintains an initially empty ArrayList L of integers, an initially unmarked flag, and the following operations: INSERT(X) Add x to the end of L. Mark the flag. EXTRACT-MAX() If the flag is marked, bubble-sort L and unmark the flag. Remove the last integer from L. 2b. Lazy-Set [8 points] Lazy-Set maintains an initially empty vector v of integers and the following operations: INSERT(X) Add x to the end of v. FIND(x) Perform a linear search of v for x. If x is found, PARTITION v on pivot x and return true; else return false. 2c. Lazy-Array [8 points] Lazy-Array maintains two initially empty ArrayList S: UNSORTED and SORTED. INSERT(X) Adds x to the back of UNSORTED. FIND(x) Does a binary search for x in SORTED; if that fails, does a linear search for x in UNSORTED. In either case, if UNSORTED is not empty, then its elements are inserted, one by one, into the SORTED array, as in insertion sort