Can anyone tell me any order for this algorithm?

Revision en6, by LODB---D, 2019-06-24 15:58:39

Hi

We have a problem on a tree.

Imagine order of our algorithm is:

Sigma x(i) ^ 2


That if we define sz[v] as number of vertices in subtree of v, x(i) is number of different sz[u] between v's children.

It's easy to see it's O(n * sqrt(n)).

But after this submission for problem 1179D I saw it was realy fast and now I think it might be better than O(n * sqrt(n)).

Any idea?

Thanks from 300iq we got that it's O(n.lg(n)) and after that by dragonslayerintraining smart proof we got it's even O(n.lg(lg(n)).

But even after these proofs I wasn't done so after running the code on problem 1179D in gym and lots of random tests the largest

Sigma x(i) ^ 2 I could find was 1032859 for n <= 500,000 (about 2 * n or n.lg(lg(n)) / 2) so now I think O(n.lg(lg(n))) might be best

order we can proof for this algorithm, how ever some one might proof it's some thing better like O(n.log*), O(n) or...

History

Revisions

Rev. Lang. By When Δ Comment
en6 LODB---D 2019-06-24 15:58:39 48 Tiny change: 'ht be best order we can \n\nproof for ' -> 'ht be best\n\norder we can proof for '
en5 LODB---D 2019-06-24 15:47:18 578 Tiny change: 'e largest Sigma x(i' -> 'e largest \nSigma x(i'
en4 LODB---D 2019-06-23 21:00:40 2 Tiny change: 'ly fast ans now I thi' -> 'ly fast and now I thi'
en3 LODB---D 2019-06-23 20:38:37 15
en2 LODB---D 2019-06-23 20:36:50 136
en1 LODB---D 2019-06-23 20:33:45 397 Initial revision (published)