Limito inferiore per la fusione di array ordinati $ m $ (conteggio delle foglie alberi decisionali - Permutazioni)

Question

Ho bisogno di aiuto per capire come calcolare il limite inferiore sulla complessità temporale della fusione $ m $ array ordinati di lunghezza $ n $.

Il limite dovrebbe essere $ nm lg (m) $. Devo dimostrarlo usando un albero decisionale.

Ho provato a contare il numero di possibili permutazioni (che sarebbe stata il numero di foglie nell'albero) ma mi sono bloccato. Ho provato quanto segue:

Quando si fondono il secondo array con il primo, abbiamo $ binom {2n} {n} $ possibilità di posizionare gli elementi. Quando si uniscono il terzo, abbiamo $ binom {3n} {n} $ E così via, quindi il numero totale di permutazioni è:

$$ binom {2n} {n} binom {3n} {n} dots binom {mn} {n} $$

L'altezza dell'albero è indicata $ H $.

$$ h> lg { binom {2n} {n} binom {3n} {n} dots binom {mn} {n}} $$

E da qui non so come dimostrare la complessità.

La mia domanda è: ho considerato correttamente le permutazioni? C'è un limite più semplice? Come continuare da qui?

Inoltre, questo dovrebbe essere probabilmente equivalente al problema di ordinare un $ m $-Aray di dimensioni ordinate $ nm $? Perché in questo problema è facile dimostrare che il limite è $ nm lg (m) $.