# Theoretical Question

## The algorithm ad its mechanism

We write the recursive function to check what kind of operation it implements on the array a.
We can apply this function to an array a = [1,2,3,4,5,6,7,8], that has a power of 2 as length, and see what kinds of 
outputs it returns for different specific lenght n, as n=2, n=4, n=8.


```python
def splitSwap( a, l, n ):
    if n <= 1:
        return
    splitSwap(a, l, n//2)
    splitSwap(a, l+ n//2, n//2)
    swapList(a, l, n)
    
def swapList(a, l, n):
    for i in range(0,n//2):
        tmp = a[l + i]
        a[l + i] = a[l + n//2 + i]
        a[l + n//2 + i] = tmp
        
a = [1,2,3,4,5,6,7,8]

splitSwap(a, 0, 2)
print(a)

a = [1,2,3,4,5,6,7,8]

splitSwap(a, 0, 4)
print(a)

a = [1,2,3,4,5,6,7,8]

splitSwap(a, 0, 8)
print(a)
```

    [2, 1, 3, 4, 5, 6, 7, 8]
    [4, 3, 2, 1, 5, 6, 7, 8]
    [8, 7, 6, 5, 4, 3, 2, 1]


We can consider only the case when l = 0 as written in the homework text. 
As shown in the previous code, the algorithm take an array a, an index l and a specific length n that could be 
different from the total length of the array a, len(a): then it returns the first n components of the array a in a 
swap order, where the first element of the first n components becomes the last and so on.

We can consider the first n components of the first array, a, as a new array, b.
The algorithm does the following things:
    
- it splits the array b into 2 arrays, 1 array composed by the first n/2 components and the second by the second 
  half of the components; then it continue on the 2 new arrays and split again this 2 arrays, and so on till this 
  split mechanism bring us to an array of only 1 component;


- now the algorithm can go back to the second last splitting and swap all the arrays with 2 components in the 
  for loop of the swapList() function, then it can join the swapped arrays of 2 components and go back to the third     last splitting with the a new 4 components arrays and so on;


- on the last step it returns to the first splitting and it joins 2 arrays of n/2 components swapped respect to 
  the starting 2 arrays, so we finally obtain the reversed b array applying swapList() on this couple of final couple 
  of arrays.
    
Finally the algorithm returns the swapped first n components of the array a and it leaves the others unchanged.

## Big O analysis

We can imagine the described previous procedure like a tree with many layers and $2^i$ branches ( the
numbers of splitted arrays at the step $i$) for the layer $i$.

If we denote the input parameter as $n = n_0$, the algorithm performs $n_0/2$ steps for each layer of the tree and the big O calculus is th following:

\begin{equation}
T(n) = 2T(n/2) + n/2 
\end{equation}

\begin{equation}
T(n) = 2( 2T(n/4) + n/4) + n/2 = 4T(n/4) + n/2 + n/2
\end{equation}

\begin{equation}
T(n) = 2^iT(n/2^i) + \sum_{k=1}^i n/2
\end{equation}

The algorithm finish to split the array when it arrives to:

\begin{equation}
n/2^i = 1   -->   i = log_2(n)
\end{equation}

so the total time is:

\begin{equation}
T(n) = nT(1) + {n\over 2}log_2(n).
\end{equation}

Finally, we have the asymptotic behavior for the splitSwap algorithm:

\begin{equation}
T(n) = O( nlog_2(n) ).
\end{equation}

because the linear term is asymptotically smaller than $nlog(n)$, so we can neglect the linear term.

## Is the algorithm optimal?

The proposed algorithm is not optimal because we can write one version with running time $T(n) = O(n)$, that is showen in the following cell.


```python
# The following version works in the case of interest, so with l = 0, and reproduce the same outputs of the 
# given version

def splitSwap( a, l, n):
    
    for i in range( 0, n//2 ):
        tmp = a[i]
        a[i] = a[n-i-1]
        a[n-i-1] = tmp
        
a = [1,2,3,4,5,6,7,8]

splitSwap(a, 0, 2)
print(a)

a = [1,2,3,4,5,6,7,8]

splitSwap(a, 0, 4)
print(a)

a = [1,2,3,4,5,6,7,8]

splitSwap(a, 0, 8)
print(a)
```

    [2, 1, 3, 4, 5, 6, 7, 8]
    [4, 3, 2, 1, 5, 6, 7, 8]
    [8, 7, 6, 5, 4, 3, 2, 1]



```python

```

8fe7e34d35d49be30431fe18bb3261c9dc245507
ipynb
Jupyter Notebook
theory.ipynb
vedatk67/ADM-HW2
1c899777a610dd03a8ed6adacc3558ffe0a629f2
MIT
theory.ipynb
vedatk67/ADM-HW2
1c899777a610dd03a8ed6adacc3558ffe0a629f2
MIT
theory.ipynb
vedatk67/ADM-HW2
1c899777a610dd03a8ed6adacc3558ffe0a629f2
MIT
Qwen/Qwen-72B
1. YES
2. YES