Is O(nk(log(k))) algorithm same as O(n(log(k))) [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question does not appear to be about programming within the scope defined in the help center.

Closed 9 years ago.

Improve this question

I was asked to give an algorithm that was supposed to be O(n(log(k))) k is the number of arrays and n is the total number of elements in all of these. I had to sort the arrays. Minus the details I came up with an algorithm that does the job for in klog(k) times the total number of elements. i.e. O(nk(log(k)))

Also in this case k is much smaller than n so it wont be n^2(logn) (in case k and n were almost same)right?

Answer 1

The way you describe the question both k and n are input parameters. If that is the case then the answer to your question is

'No, O(n*k *log(k)) is not the same as O(n*log(k))'.

It is not that hard to see that the first one grows faster than the second one, but it is even more obvious if you fix the value of n. Consider n begin a constant say 1. Than it is more obvious that O(k*log(k)) is not the same as O(log(k)).

Answer 2

Well, no, it's not the same. If k is a variable (as opposed to a constant) in the complexity expression then O(nk(log(k))) > O(n(log(k))).

That is because there is no constant C such that Cn(log(k)) > kn(log(k)) for every n, k.