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)

Answer 41 Answer 42 Computed a dlevel rotation of an array is On in best case linear time However using a circular array makes this computation consta... View the full answer