Ejercicio 1. Tenemos dos matrices, A y B, ambas de dimensión n × n, y queremos calcular la matriz C = A × B. Denotamos con A[i, ·] y B[·, j] la fila i de A y la columna j de B, respectivamente. Para resolver el problema contamos con el algoritmo:
1 for i = 1 to n do
2 for j = 1 to n do
3 Calcular el producto escalar < A[i, ·], B[·, j] >
4 Guardar el resultado en C[i, j]
5 end
6 end
Dé explícitamente una función f tal que el tiempo de ejecución de este algoritmo es Θ(f(n)); justifique su respuesta demostrando el resultado
Esta función se cumpliría para el algoritmo planteado
Θ(g(n)) = {f(n) : ∃c,d ∈ R +,∃nₒ ∈ N, tal que cg(n) ≤ f(n) ≤ dg(n) para todo n ≥ nₒ}
c y d son dos constantes
n: tiene que ver con la cantidad de filas y columnas que van de 1 a n.
Como existen dos interacciones for y luego se debe almacenar los resultados en la matriz según el paso 6, se asume que g(n)= n3 y se debe comprobar que g(n)= n3€ Θ(f(n)
Llegue hasta aqui, pero me tranque. Asumie que cumple un g(n)=n(elevado)3. ¿Es así? Si no, ¿por que estoy equivocado?Gracias
