Sorting

Question

What is the time complexity to divide an array of elements N into $Log N$  parts ? plz explain ?

Comments

@Rohit1

You are right. I took it as different. We can divide into $Log N$ parts and every part comtaīns elements in the power of $2$.

I had solved one similar question https://gateoverflow.in/65147/gatebook-exam

---

If we divide N element array into logN parts then each part gets $\frac{N}{logN}$ elements. Index of first part starts at 0 continues upto $\frac{N}{logN} - 1$

second at $\frac{N}{logN}$ to $\frac{2N}{logN} - 1$

 third at $\frac{2N}{logN}$ to $\frac{3N}{logN} - 1$

It includes only calculation of logN  indices.

Correct me if I'm doing something wrong.

---

He is asking for only partition, Can't we just calculate $LogN$ and partition indices of array either from start or end? Please tell.

---

Thinking same bro.

Answer 1

The answer would be nloglogn

As we have seen when array of size N is divided into k arrays having size n then time complexity becomes O(nklogk)

Now we can replace values according to our given question which will results to O(NloglogN)

Answer 2

Each division will take O(1) time. In first stage there is only 1 division, next stage there are 2 divisions, then 4 then 8 and so on. In last stage we need loglogN divisions.

We can write each division size of last stage N/logN = N/(2^loglogN).

So we get series like 1+2¹+2²+2³+2⁴+....+loglogN ( loglogN = 2^logloglogN ) . Now by solving the G.P series we get O(loglogN).