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

Question

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. closest pair/ sorting.

Answer 1

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.