can anyone tell me any order for these kind of algorithms

Revision en1, by Mahdi_Hajibeygi, 2019-06-23 20:33:45

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 as I saw it was realy fast I think it's just better.

Any idea?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English Mahdi_Hajibeygi 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 English Mahdi_Hajibeygi 2019-06-24 15:47:18 578 Tiny change: 'e largest `Sigma x(i' -> 'e largest \n`Sigma x(i'
en4 English Mahdi_Hajibeygi 2019-06-23 21:00:40 2 Tiny change: 'ly fast ans now I thi' -> 'ly fast and now I thi'
en3 English Mahdi_Hajibeygi 2019-06-23 20:38:37 15
en2 English Mahdi_Hajibeygi 2019-06-23 20:36:50 136
en1 English Mahdi_Hajibeygi 2019-06-23 20:33:45 397 Initial revision (published)