How can I prove a lower bound that is \Omega{(n (logn)^k)} ? [k>1]

There are many algorithms run in O(n {log n}^k)-time, where k>1.

It would be very helpful if you could provide me some reference about any problem that has:

\Omega{(n {log n}^k)} lower bound, where k>1.

I know that there are many examples for k=1, e.g. c开发者_StackOverflow社区losest pair/ sorting.

---

Here is a contrived example for k=2.

You have an nxn array. Each row of the array is sorted.

Each row has the property that every element in the row occurs an even number of times (in that row), except one, which occurs an odd number of times in that row.

Find the "odd" element of each row.

This has provable Omega(n log^2 n) lower bounds (and has O(n log^2 n) algorithms).

For the case of 1 row, we have the proof right here (on stackoverflow) : How can I find a number which occurs an odd number of times in a SORTED array in O(n) time? which proves Omega(log^2 n) lower bounds. It easily proves the lower bound for this problem.