Andrés Cruz Chipol

Tarea 2: Problema: Para cada función f(n) y tiempo t en la siguiente tabla, determine el tamaño de n más grande para un problema que puede ser resuelto en un tiempo t, asumiendo que el algoritmo toma f(n) microsegundos para resolver el problema.

Fecha de entrega: jueves 18 de septiembre, 2025

Introducción y Aclaraciones

Para resolver este problema, primero convertimos cada unidad de tiempo a microsegundos, ya que el costo del algoritmo está dado en microsegundos.

Definiciones:

  • Microsegundo = µs = 10⁻⁶ segundos
  • Milisegundo = ms = 10⁻³ segundos
  • En este problema trabajamos con microsegundos (µs)

Equivalencias básicas:

  • 1 s = 1,000,000 µs = 10⁶ µs
  • 1 min = 60 s
  • 1 h = 60 min
  • 1 día = 24 h
  • 1 mes ≈ 30 días
  • 1 año ≈ 365 días
  • 1 siglo = 100 años

Conversiones a Microsegundos

Tiempo t (μs) Cálculo
1 segundo 1.0×10⁶ μs 1 s × 10⁶ μs/s
1 minuto 6.0×10⁷ μs 60 s × 10⁶ μs/s
1 hora 3.6×10⁹ μs 3600 s × 10⁶ μs/s
1 día 8.64×10¹⁰ μs 86,400 s × 10⁶ μs/s
1 mes (≈30 días) 2.592×10¹² μs 30 × 8.64×10¹⁰ μs
1 año (≈365 días) 3.1536×10¹³ μs 365 × 8.64×10¹⁰ μs
1 siglo (100 años) 3.1536×10¹⁵ μs 100 × 3.1536×10¹³ μs

Despejes de cada Función

Para encontrar el tamaño máximo n que puede ser procesado en tiempo T, despejamos n de cada función f(n) ≤ T:

1. log₂ n: \( \log_2(n) \leq T \;\;\Rightarrow\;\; n \leq 2^T \)

2. √n: \( \sqrt{n} \leq T \;\;\Rightarrow\;\; n \leq T^2 \)

3. n: \( n \leq T \)

4. n log₂ n: No tiene despeje cerrado → se resuelve por aproximación numérica (búsqueda binaria)

// Algoritmo de búsqueda binaria para n log n
function f_nlogn(T) {
  let low = 1, high = T;
  while (low < high) {
    let mid = Math.floor((low + high + 1) / 2);
    if (mid * Math.log2(mid) <= T) {
      low = mid;
    } else {
      high = mid - 1;
    }
  }
  return low;
}

5. n²: \( n^2 \leq T \;\;\Rightarrow\;\; n \leq \sqrt{T} \)

6. 2ⁿ: \( 2^n \leq T \;\;\Rightarrow\;\; n \leq \log_2(T) \)

7. n!: No tiene despeje cerrado → se resuelve por aproximación numérica (factoriales crecientes)

// Algoritmo iterativo para n!
function f_factorial(T) {
  let n = 1, fact = 1;
  while (fact <= T) {
    n++;
    fact *= n;
    if (fact > T) break;
  }
  return n - 1;
}

Tabla de Resultados

Tiempo (T) lg n √n n n lg n n² 2ⁿ n!
1 segundo
(1.0×10⁶ μs)		 2^(10⁶) ≈ 10^(3.01×10⁵) 1.0×10¹² 1.0×10⁶ ≈ 62,746 1,000 19 9
1 minuto
(6.0×10⁷ μs)		 2^(6×10⁷) 3.6×10¹⁵ 6.0×10⁷ ≈ 2,802,000 7,745 25 11
1 hora
(3.6×10⁹ μs)		 2^(3.6×10⁹) 1.296×10¹⁹ 3.6×10⁹ ≈ 1.33×10⁸ 60,000 31 12
1 día
(8.64×10¹⁰ μs)		 2^(8.64×10¹⁰) 7.46×10²¹ 8.64×10¹⁰ ≈ 2.75×10⁹ 293,938 36 13
1 mes
(2.592×10¹² μs)		 2^(2.592×10¹²) 6.72×10²⁴ 2.592×10¹² ≈ 7.19×10¹⁰ 1.61×10⁶ 41 15
1 año
(3.1536×10¹³ μs)		 2^(3.15×10¹³) 9.95×10²⁶ 3.1536×10¹³ ≈ 7.98×10¹¹ 5.62×10⁶ 44 16
1 siglo
(3.1536×10¹⁵ μs)		 2^(3.15×10¹⁵) 9.95×10³⁰ 3.1536×10¹⁵ ≈ 6.86×10¹³ 5.62×10⁷ 51 17

Análisis y Conclusiones

Los resultados muestran claramente cómo diferentes funciones de complejidad temporal permiten procesar tamaños de problema vastamente diferentes para el mismo tiempo disponible:

  • Algoritmos logarítmicos (log n): Permiten tamaños de problema astronómicamente grandes, prácticamente sin límite para tiempos razonables.
  • Algoritmos de raíz cuadrada (√n): También permiten tamaños muy grandes, especialmente para tiempos largos.
  • Algoritmos lineales (n): El tamaño máximo del problema es directamente proporcional al tiempo disponible.
  • Algoritmos n log n: Ligeramente más restrictivos que los lineales, pero aún muy escalables.
  • Algoritmos cuadráticos (n²): Mucho más limitados, el crecimiento se vuelve problemático rápidamente.
  • Algoritmos exponenciales (2ⁿ): Extremadamente restrictivos, solo permiten problemas muy pequeños.
  • Algoritmos factoriales (n!): Los más restrictivos de todos, prácticamente inviables para n > 20.

Esto nos ilustra la importancia de escoger un algoritmo eficiente para la solución de nuestros problemas, principalmente cuando trabajamos con datos con bastante volumen de información que puede afectar el costo.