# TDA | practica 2 ejercicio 1
## Consigna
Escriba un algoritmo con dividir y conquistar que determine si un arreglo de tamaño potencia de \(2\) es "más a la izquierda", donde "más a la izquierda" significa que:
1. La suma de los elementos de la mitad izquierda superan los de la mitad derecha.
2. Cada una de las mitades es a su vez "más a la izquierda".
Por ejemplo, el arreglo \([8, 6, 7, 4, 5, 1, 3, 2]\) es "más a la izquierda", pero \([8, 4, 7, 6, 5, 1, 3, 2]\) no lo es.
Intente que su solución aproveche la técnica de modo que la complejidad del algoritmo sea estrictamente menor a $O(n^2)$.
## Resolución
### Codigo
```python
def Z(A:list)->bool:
a = len(A)
# caso base:
if a == 1:
return True
# Divide:
mitad = a // 2
mitadIzquierda = A[:mitad]
mitadDerecha = A[mitad:]
sumaIzquierda = sum(mitadIzquierda)
sumaDerecha= sum(mitadDerecha)
# Conquer:
if sumaIzquierda > sumaDerecha and Z(mitadIzquierda) and Z(mitadDerecha):
return True
else:
return False
```
- Teorema maestro:
- $a=2$, $b=2$
- $T(n) = 2T(\frac{n}{2}) + O(n)$
- El $O(n)$ se debe a que las sum de python son lineales, los slicing tengo entendido que son constantes.
- $log_2(2) = 1 \Rightarrow O(n \ log \ n)$