CODEWITHSUNDEEP
algorithmcomplexity-theorybig-o
AShelly
AShelly

Reputation: 35580

What is the Big-O of this two-part algorithm?

Given the following algorithm on a dataset of size N:

  1. Separate the data into M=(N/lg N) blocks in O(N) time.
  2. Partition the blocks in O(M lg M) time. *

What is the big-O? How do I evaluate (N/lg N) * lg (N/lg N) ?

If it is not O(N), is there an M small enough that the whole thing does become O(N)?

* The partition algorithm is the STL's stable_partition which, in this example, will do M tests and at most M lg M swaps. But, the items being swapped are blocks of size lg N. Does this push the practical time of step 2 back up to O(N lg N) if they must be swapped in place?

Not homework, just a working engineer poking around in comp-sci stuff.

Upvotes: 2

Views: 397

Answers (2)

justhecuke
justhecuke

Reputation: 1185

You evaluate by doing a bit of math.

log(x/y) = log(x) - log(y)
->
log(N / log(N)) = log(N) - log(log(N))

So, plugging this back in and combining into a single fraction.
N(log(N) - log(log(N))) / log(N)
=
N - N(log(log(N)) / log(N))
<=, since log(log(N)) <= log(N) as N -> inf., it's like multiplying by <= 1
N

So, the whole thing is O(N).

You can pretty easily guess that it is O(N log N) by noticing that M = N / log N is, itself, O(N). I don't know of a quick way to figure out that it's O(N) without a bit of doubt on my part due to having to multiply in the log M.

Upvotes: 4

maxim1000
maxim1000

Reputation: 6365

It is O(N):

N / lgN * lg(N / lgN)=N / lgN * (lgN-lglgN)=N*(1-lglgN / lgN)<=N

Upvotes: 2

Related Questions