Tempo medio rispetto al peggiore dei casi

Question

Prendi in considerazione una semplice passeggiata casuale su un grafico non orientato e lascia che $ h_ {ij} $ sia il tempo di successo da $ i $ a $ j $. Quanto può più grande $$ h _ { rm max} = max_ {i, j} h_ {ij}, $$ deve essere paragonato a $$ h _ { rm Ave} = frac {1} {n^2} Sum_ {i = 1}^n sum_ {j = 1}^n h_ {ij}. $$ Per tutti gli esempi a cui riesco a pensare, queste due quantità hanno circa lo stesso ordine di grandezza.

Per trasformarlo in una domanda formale, definisce $$ phi (n) = max _ { mbox {grafici non diretti con} n mbox {nodes}} frac {h _ { rm max} {h _ { rm aveve }}. $$ Quanto velocemente $ phi (n) $ cresce con $ n $?