8.1-4

Suppose that you are given a sequence of n elements to sort. The input sequence consists of n/k subsequences, each containing k elements. The elements in a given subsequence are all smaller than the elements in the succeeding subsequence and larger than the elements in the preceding subsequence. Thus, all that is needed to sort the whole sequence of length n is to sort the k elements in each of the n/k subsequences. Show an $ \Omega(n lg k)$ lower bound on the number of comparisons needed to solve this variant of the sorting problem. (Hint: It is not rigorous to simply combine the lower bounds for the individual subsequences.)
let $h_k$ be height of the subtree tree of k elements and l be the reachable leaves $$k! \leq l \leq 2^h $$ applying log on both sides $$ log k! \leq log 2^h_k $$ $$ log k! \leq h_k $$ The above height is one sub tree we have n/k subsequences. Add n / k subsequences of log k! height. $$ n/k log k! \leq h $$ since log k can be written as k log k as per stirlings approximation or bounding it using integrals $$ n/k . k log k \leq h $$ $$ n log k \leq h $$ since h is no of comparisons as well as height as per lower bound for worst case on pg 193 $$ h = \Omega(n log k) $$