Sum of sqrt of (size_of_subtree) in tree

Revision en15, by PouyaNavid, 2020-05-31 16:32:57

Hi,

Consider a rooted tree

size(v) = number of vertices in subtree of v

Any good limit on $$$\sum_{i=1}^{n} $$$$$$\sqrt{size(i)}$$$ ?

like

$$$O(n \log n)$$$

$$$O(n \log \log n)$$$

$$$O(n)$$$

...

UPD :

b(v) is a son of v with the largest subtree size.

limit on $$$\sum_{i=1}^{n} $$$$$$\sqrt{size(i) - size(b(i))}$$$ ?

Tags #tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en15 English PouyaNavid 2020-05-31 16:32:57 2 Tiny change: '*UPD :**\n\n\n**_b(v' -> '*UPD :**\n \n\n**_b(v'
en14 English PouyaNavid 2020-04-03 11:10:46 2 Tiny change: '(i))}$ ?\n' -> '(i))}$ ?\n\n'
en13 English PouyaNavid 2020-04-03 11:10:10 1 Tiny change: '\n$O(n)$\n\n...\n \n' -> '\n$O(n)$\n \n...\n \n'
en12 English PouyaNavid 2020-04-02 11:24:53 1 Tiny change: '$\n\n...\n\n \n \n**' -> '$\n\n...\n \n \n \n**'
en11 English PouyaNavid 2020-03-30 07:47:06 1 Tiny change: 'ted tree\n\n**_size(' -> 'ted tree\n \n**_size('
en10 English PouyaNavid 2020-03-29 16:08:34 1 Tiny change: 'n\n...\n\n\n \n**UPD' -> 'n\n...\n\n \n \n**UPD'
en9 English PouyaNavid 2020-03-28 20:19:20 1 Tiny change: 'n...\n\n\n\n**UPD :*' -> 'n...\n\n\n \n**UPD :*'
en8 English PouyaNavid 2020-03-28 13:14:44 1 Tiny change: 'btree of v\n\nAny go' -> 'btree of v \n\nAny go'
en7 English PouyaNavid 2020-03-27 17:32:23 2 Tiny change: '}$ ? \n\nlike\n' -> '}$ ? \n\n\nlike\n'
en6 English PouyaNavid 2020-03-27 11:39:22 2 Tiny change: 'n...\n\n\n**UP' -> 'n...\n\n\n\n**UP'
en5 English PouyaNavid 2020-03-26 19:38:00 2 Tiny change: 'ze(b(i))}$\n' -> 'ze(b(i))}$ ?\n'
en4 English PouyaNavid 2020-03-26 11:43:02 38 Tiny change: 'e\n\n\n$O(N*LOG)$\n\n$O(N' -> 'e\n\n\n$O(n \log)$\n\n$O(N'
en3 English PouyaNavid 2020-03-26 10:53:20 134 Tiny change: '\nlimit on($\sum_{i=1' -> '\nlimit on $\sum_{i=1'
en2 English PouyaNavid 2020-03-26 10:13:33 2 Tiny change: '**Hi,\n\nCon' -> 'Hi,\n\nCon'
en1 English PouyaNavid 2020-03-26 10:13:22 248 Initial revision (published)