This is a repost of a question by me earlier(which I deleted as it had less details),
Consider the following algorithm (phone call model) of spreading a gossip/rumor -
On day $1$, only $1$ person knows the rumor, he calls randomly independently a person in the city of total $n$ persons and tells the rumor to that person. The process is repeated by all those that know the rumor on a given day (each knower calls a single person daily,who may or may not know the rumor already). This is repeated till all know the rumor after some days.
I want to show the expected duration till all people in the city know, is $O(\log n)$.
I wish to know if the following approach is correct :
At any day, suppose I have $k$ number of people who know the rumor, and $T_{k+1}$ be the time(day number) when a new $(k+1)^{th}$ member comes to know.
Then since, at this instant, for any person who knows the rumor, probability of selecting new person to inform rumor is $\frac{n-k}{n-1}$, and by linearity of expectation, number of new person increased in a day $= \frac {k(n-k)}{n-1} = d$(say).
So time to get one additional member who knows is $= 1/d = E(T_{k+1} - T_{k}) $, as it is a geometric variable, then I can apply $E(T_n) = \sum_{k=0}^{k=n-1}E(T_{k+1}- T_k) $to get $E(T_n) =$ harmonic number $\approx \ln n$