4 [w] Dynamic Arrays Consider a 2-level rotated array data structure representing the array A =...

Transcribed Image Text:

4 [w] Dynamic Arrays Consider a 2-level rotated array data structure representing the array A = [8, 11, 2, 3, 4,9, 8, 1]. Solve the following exercises. 4.1 Draw the 2-level rotated array. Use n 3. 4.2 Show how to compute the rotated array R, and index k in R, corresponding to an index i in A. Both should be constant time. 4.3 Show the result of each of the operations insert(5, 42), delete(2), delete(6). 4 [w] Dynamic Arrays Consider a 2-level rotated array data structure representing the array A = [8, 11, 2, 3, 4,9, 8, 1]. Solve the following exercises. 4.1 Draw the 2-level rotated array. Use n 3. 4.2 Show how to compute the rotated array R, and index k in R, corresponding to an index i in A. Both should be constant time. 4.3 Show the result of each of the operations insert(5, 42), delete(2), delete(6).

Answer rating: 100% (QA)

Solution 41 42 Calculated a d level rotation of an array is O n in finest case linear time But using a circular array builds this computation constant ... View the full answer