## Ejercicios Big O()
### 1. Calcule el costo T(n) para la siguiente función.
        A. Grafique la función junto con otros O() clásicos.
        B. Analice los cambios a medida que el n aumenta.
        C. T(n) esta incluido en la familia de O(n)? Justifique utilizando definición de O().
        D. El costo obtenido es aceptable?
        
A continuación un ayuda memoria de $O()$ en operaciones sobre Python:


```python
from IPython.display import IFrame
IFrame('https://wiki.python.org/moin/TimeComplexity', width=900, height=350)


```











```python
def dummy_func(lst, n):
    print("primer elemento", lst[0]) 
    
    midpoint = int(n / 2)
    
    for val in lst[:midpoint]:
        print(val)
        
    for x in range(10):
        print('o_O')
```


```python
dummy_func([1, 2, 3, 4], 4)
```

    primer elemento 1
    1
    2
    o_O
    o_O
    o_O
    o_O
    o_O
    o_O
    o_O
    o_O
    o_O
    o_O


1.A)
Analizando las lineas de la función dada podemos ver que:
- En linea 2 tenemos $O(1)$
- En linea 4 tenemos $O(1)$
- En linea 6 y 7 tenemos $O(n/2)$
- En linea 9 y 10 tenemos $O(10)$

Por lo que nuestro $O(n/2 + 12)$



1.B) Ahora graficaremos $O(n/2 + 12)$ junto con $O(n)$, $O(n \log n)$, $O(n^2)$, $O(2^n)$


```python
from math import log
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
plt.style.use('default')

# Set up runtime comparisons

n = np.linspace(1, 100, 1000)
labels = ['Lineal', 'Lineal Log', 'Cuadrática','Exponencial', 'Mi T(n)']
big_o = [n, n* np.log(n), n**2, 2**n, n/2 + 12]

# Plot setup
plt.figure(figsize=(12,10))
plt.ylim(0, 700)
plt.xlim(1, 100)

for i in range(len(big_o)):
    plt.plot(n,big_o[i],label = labels[i])


plt.legend(loc=0)
plt.ylabel('Tiempo relativo de ejecución')
plt.xlabel('n')
```

 1.C) Podemos observar que nuestra función con $n_0 = 24, c=1$ $ \rightarrow T(n) \in O(n)\; \forall\; n \geq 24$:
 
 \begin{equation}
 n/2 + 12 \leq c.n \; \forall\; n \geq 24 \\
 n/2 + 12 \leq n \; \forall\; n \geq 24 \\ 
 \end{equation}

1.D)


Imagen de http://bigocheatsheet.com/

### 2. Desarrolle dos funciones en Python para encontrar el número más chico en una lista. La primer función debería comparar cada número entre si ($O(n^2)$). La segunda función debería ser lineal ($O(n)$).
        A. Grafique ambas funciones.
        B. Con que implementación se quedaría?
        C. Hay correspondencia entre el benchmarking y $O()$. 


```python
def min_value_n2(lst):
    min_value = lst[0] # O(1)
    for i in lst:      # O(n)
        for j in lst:  # O(n)
            if i < j:  # O(1)
                min_value = i   # O(1)
            elif j < i:         # O(1)
                min_value = j   # O(1) 
    return min_value            # O(1)

min_value_n2([3, 2, 6, 1])
# O(4*n^2 + 2)
```




    1




```python
def min_value_n(lst):
    min_value = lst[0]        # O(1)
    for i in lst:     # O(n)
        if i < min_value:     # O(1)
            min_value = i     # O(1)
    return min_value          # O(1)

min_value_n([3, 2, 6, 1])
# O(2*n + 2)
```




    1



2.A)


```python
from math import log
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
plt.style.use('default')

# Set up runtime comparisons

n = np.linspace(1, 100, 1000)
labels = ['min_value_n', 'min_value_n2']
big_o = [2*n + 2, 4*n**2 + 2]

# Plot setup
plt.figure(figsize=(12,10))
plt.ylim(0, 700)
plt.xlim(1, 100)

for i in range(len(big_o)):
    plt.plot(n,big_o[i],label = labels[i])


plt.legend(loc=0)
plt.ylabel('Tiempo relativo de ejecución')
plt.xlabel('n')
```

2.C)


```python
assert(min_value_n([3, 2, 6, 1]) == min_value_n2([3, 2, 6, 1]))
```


```python
%timeit min_value_n(range(10000))
```

    1000 loops, best of 3: 362 µs per loop



```python
%timeit min_value_n2(range(10000))
```

    1 loop, best of 3: 5.51 s per loop


dd14c07efb73195815ce52f7a5882558ece5f5ac
ipynb
Jupyter Notebook
Ejercicios_big_o.ipynb
celiacintas/FTI
2c52681e3ed2d5a284aaaaca83e21bb9bb742620
MIT
2017-07-31T00:41:12.000Z
2017-07-31T00:41:12.000Z
Ejercicios_big_o.ipynb
celiacintas/FTI
2c52681e3ed2d5a284aaaaca83e21bb9bb742620
MIT
Ejercicios_big_o.ipynb
celiacintas/FTI
2c52681e3ed2d5a284aaaaca83e21bb9bb742620
MIT
Qwen/Qwen-72B
1. YES
2. YES