Lo que usted necesita para estar hablando de un es $\displaystyle \Omega(f+g)$ e no $\Omega(f) + \Omega(g)$ $\Omega(f)$ $\Omega(g)$ son conjuntos.
Si $\displaystyle |h(x)| \ge c_1 |f(x)|$$\displaystyle |h(x)| \ge c_2 |g(x)|$, entonces tenemos que
$\displaystyle |h(x)| \ge \frac{c}{2} (|f(x)| + |g(x)|) \ge c' |f(x) + g(x)|$ donde $\displaystyle c = \text{min}\{c_1, c_2\}$.
Por lo tanto si $\displaystyle h \in \Omega(f)$$\displaystyle h \in \Omega(g)$,$h \in \Omega(f+g)$.
Pero en tu caso, incluso si usted tiene un número variable de sub-problemas, no estoy realmente seguro de que estoy completamente de acuerdo con Alon.
Realmente depende de lo que usted considere variable cuando se considera cada sub-problema.
Si $n,k$ son las variables, y usted tiene una constante de $c$ (independiente de $n$$k$), tales que cada una de las $\frac{n}{k}$ independiente sub-problemas es de tamaño al menos $c k \log k$, entonces usted puede agregar a ellos de la manera que usted lo hizo, para obtener el tamaño total.
Por ejemplo, considerar el problema en una matriz es casi ordenada: cada elemento está dentro de $k$ de su posición original. Usted puede ordenar la matriz de clasificación de $\frac{n}{k}$ trozos de $2k$ elementos de cada uno. Si usted quería considerar el tiempo total empleado, por ejemplo, con el algoritmo que se han elegido para la clasificación, cada fragmento siempre tarda $\Omega(k\log k)$ del tiempo, entonces el tiempo total es de hecho $\Omega(n \log k)$.
Si usted tuvo la $i^{th}$ subproblem constante, ser una función de la $i$, entonces no es realmente una constante, ya que depende de $\frac{n}{k}$.
Ahora si se permite la $i^{th}$ sub-problema constante para ser independiente de $k$, pero no $n$, entonces la adición de ellos se convierte en una especie de sentido y podría conducir a resultados incorrectos, como Alon señaló.
Nota: Si usted estaba tratando de probar un $\Omega(n \log k)$ límite inferior para la clasificación en el problema anterior, considerando a $n/k$ sub-problemas de tamaño de la $k$, sólo añadir como que no es una prueba de que en general los límites inferiores. En el peor de los casos, cada sub-problema podría ser $\Omega(k \log k)$, pero cuando se pulse el peor de los casos para un sub-problema, usted podría estar golpeando el mejor de los casos para otro. Así que incluso afirmando $\Omega(k \log k)$ inferiores a los límites para cada sub-problema necesita más pruebas.
Usted puede agregar hasta para los límites superiores, aunque. Se puede decir que un algoritmo sería $\mathcal{O}(n \log k)$ en el peor de los casos (por ejemplo, si has elegido el heap-sort), aunque algunos sub-problema podría tomar $\mathcal{o}(k \log k)$ comparaciones (nota: pequeñas oh), el número total de comparaciones es esencialmente $\mathcal{O}(n \log k)$.
