$\backslash$problem$[$Search and insertion through multiple

sorted arrays$]\{5+2+4+4\}$

If we are given a sorted array with $n$ elements, it is

straightforward to search for an element in $O$(\backslash$log n$)$$$.$ However, if

we want to insert a new element $x$ to a sorted array, while the

position to where to insert $x$ can be found in $O$(\backslash$log n$)$$ time,

performing the actual insertion could take $$\backslash$Omega$($n$)$$ time since we

need to shift the elements in the array to accommodate the new

element.

One approach to address the above problem is to maintain

$\backslash$emph$\{$multiple sorted arrays$\}.$ Let $S$ denote a dynamic set of

elements that we are maintaining, and let $n $=|$S$|$$$.$ Then, we will

store $S$ using $k$ sorted arrays $L$\_0$$$,$ $L$\_1$$$,\backslash$ldots$,$ $L$\_\{$k$-1\}$$

where $k$ is the number of bits in the binary representation of $n$$,$

given by $n$\_\{$k$-1\}\backslash$cdots n$\_0$$$.$ The size of array $L$\_$i$ will be $$2^$i$$.$

If the $n$\_$i$ is $0,$ then the array $L$\_$i$ will be empty $($have no

elements$).$ If the $n$\_$i$ is $1,$ then the array $L$\_$i$ will be full and

contain $$2^$i$ elements of $S$$.($You may assume that all elements of

$S$ are distinct.$)$

oindent $\backslash$textbf$\{$Example:$\}$ Suppose we have a set $S$ of $n $=43$$

elements. The binary representation of this is $$101011$$$.$ So these $43$

elements will be stored in $6$ sorted arrays: a full sorted array $L$\_0$$

with $1$ element, a full sorted array $L$\_1$$ with $$2$$ elements, an empty

array $L$\_2$$$,$ a full sorted array $L$\_3$$ with $8$ elements, an empty array

$L$\_4$$$,$ and a full sorted array $L$\_5$$ with $32$ elements. Here is an

example. $($Note that while each array is sorted, elements in different

arrays bear no particular relationship to one another.$)\{\backslash$small

$\backslash [$

L$\_0=[16]\backslash$;$\backslash$; L$\_1=[14,73]\backslash$;$\backslash$; L$\_2=[]\backslash$;$\backslash$; L$\_3=[1,4,6,10,15,42,67,90]\backslash$;$\backslash$; L$\_4=[]\backslash \backslash$

$\backslash ]$

$\backslash [$

L$\_5=[2,5,8,11,12,19,21,22,23,24,$

$25,30,32,34,35,41,43,49,51,53,$

$59,60,62,63,64,66,68,70,71,74,$

$77,78]$

$\backslash ]$

$\}$ When a new element is inserted, the number of elements will increase

to $$44$$$,$ which has a binary representation of $$101100$$$,$ implying that

we will reorganize the elements so that we have full sorted arrays

$L$\_5$$$,$ $L$\_3$$$,$ and $L$\_2$$$.$ You need to figure out how to reorganize

these in the most efficient manner. $(\{\backslash$em Hint:$\}$ In this example, you

can do this by processing only $4$ elements, including the newly

inserted one.$)$

$\backslash$begin$\{$enumerate$\}$

$\backslash$item Describe an algorithm for inserting a new element to

set $S$ with $n$ elements stored using the above method $($the new

element is the $$($n$+1)$$th element$).$ In particular, describe how you

will reorganize the sorted arrays to maintain the binary

representation property in the $\backslash$emph$\{$most efficient way$\}.$ It

suffices to describe your algorithm in words. You do not need to

provide pseudocode. $(\{\backslash$em Hint:$\}$ If $L$\_0$$ is empty, it is straightforward what to do$.$

Otherwise, use the binary representations of $n$ and $n$+1$$ to

determine which sorted lists to merge, along with the new element,

to create a new sorted list. It may be help to work with examples

for small $n$$.)$

To insert a new element into the set $\backslash ($ S $\backslash )$ using the multiple sorted arrays method:

$1.$ First, I look at the binary representation of $\backslash ($ n $\backslash )($the current number of elements$)$ and $\backslash ($ n$+1\backslash )($after inserting the new element$).$ This helps me see which arrays need updating.

$2.$ I find the highest bit position where $\backslash ($ n $\backslash )$ and $\backslash ($ n$+1\backslash )$ differ in binary. This tells me which arrays $\backslash ($ L$\_$i $\backslash )$ and above need adjustment.

$3.$ I take the arrays from $\backslash ($ L$\_$i $\backslash )$ up to $\backslash ($ L$\_\{$k$-1\}\backslash )($where $\backslash ($ k $\backslash )$ is the number of bits in $\backslash ($ n $\backslash ))$ and merge them with the new element. This creates larger arrays that stay sorted.

$4.$ I update the binary representation of $\backslash ($ n $\backslash )$ to $\backslash ($ n$+1\backslash )$ by marking the arrays that are now full $($where elements were added$).$

$5.$ To keep it efficient, I merge arrays in a way that minimizes the number of operations, focusing on adjacent arrays or combining smaller arrays into larger ones.

This method ensures I insert the new element while keeping all arrays sorted and adjusting the structure in $\backslash ($ O$(\backslash$log n$)\backslash )$ time, which is efficient for maintaining sorted sets in dynamic scenarios.

$\backslash$item Analyze the worst$-$case running time of your

algorithm, for inserting a new element to set $S$ with $n$ elements.

When I insert a new element into the set $\backslash ($ S $\backslash )$ that has $\backslash ($ n $\backslash )$ elements stored in $\backslash ($ k $\backslash )$ sorted arrays:

$1.$ First, I update the binary representation from $\backslash ($ n $\backslash )$ to $\backslash ($ n$+1\backslash ).$ This step takes $\backslash ($ O$(\backslash$log n$)\backslash )$ time to decide which arrays need adjustments.

$2.$ I might need to merge up to $\backslash ($ k $\backslash )$ arrays. Each merge involves combining two sorted arrays into one. Since the array sizes double during merging $($from $\backslash (2^$i $\backslash )$ to $\backslash (2^\{$i$+1\}\backslash )),$ each merge operation can take up to $\backslash ($ O$(2^$i$)\backslash )$ time.

$3.$ In the worst case, where all $\backslash ($ k $\backslash )$ arrays require merging, the insertion can take $\backslash ($ O$(\backslash$log n $\backslash$cdot $2^$k$)\backslash )$ time.

$4.$ Despite the worst$-$case complexity, the average time per insertion remains $\backslash ($ O$(\backslash$log n$)\backslash ).$ This i