Since we are using InsertionSort, we can assume only that the data
can be compared.  Given this, the lowerbound of n log n for sorting
applies.  Since we are told that going from a k-away-sorted list to
a fully sorted list is order nk, logically this tells us that the
lower bound to create the a k-away-sorted list would be the lower
bound of sort (n log n) minus that nk cost.

So, n log n - n * k or n * (log n  -  k) would be a lower bound
identified with this information.

Of course, this does not tell us whether this lower bound can actually
be achieved, or whether a more precise lower bound could be found with
a different approach.