Problem 2. (8 points) Provide a full runtime analysis for the LinkedVector::rebalance method based on the pseudocode algorithm provided in section 4.2.3 under the programming problem. In addition to the analysis, provide a tight Big-O bound for the method.

4.2.3 When and How to Rebalance The following conditions must be maintained during insertion: Insertion should maintain that for each i,0siSk:i10(k+1). If this is violated, a call should be made by insert to rebalance. . Insertion of an item that could go at the end of the data vector in one node or at the start of the data vector of the neighboring node should insert into the node with the smaller size (see section 4.2.4 regarding insertion of 42 for illustration). In the event of a tie, insert into the left node. 4.2.3 When and How to Rebalance The following conditions must be maintained during insertion: Insertion should maintain that for each i,0siSk:i10(k+1). If this is violated, a call should be made by insert to rebalance. . Insertion of an item that could go at the end of the data vector in one node or at the start of the data vector of the neighboring node should insert into the node with the smaller size (see section 4.2.4 regarding insertion of 42 for illustration). In the event of a tie, insert into the left node