one example on game playing with some details, how this average step was calculated? I have one example in my TA notes:
We have a two players games. two players will be agree on number $n$. game start with $x=2$. first player select by Coin flipping and start game. after that each of players arbitrary do one of the following: $x=x^2$ or $x=x^3$.
for example if "David" start game and choose $x^3$ then $x$ will be equals to $8$. after playing of each players that condition $x>n$ occurred, the game will be stopped and the last player announced as winner. at average this game ended after $O(\log \log n)$ steps.
This is very nice example, but how we can detect this average order can be achieved?
 A: If we take $\log_2$ of everything, we end up with a simpler game that is equivalent to the original ($\log$ is monotonically increasing, so $x>n$ iff $\log x > \log n$). I will denote $\log_2x$ by $y$ and $\log_2n$ by $m$. When we take the log, squaring becomes doubling, and cubing becomes tripling.
Then this game is equivalent to the following:
Start with $y=1$. The players take turns either doubling or tripling $y$. The game ends when $y >m$.
We can take the log again. When we take the log of a product, that's the sum of the log of the multiplicands, so doubling becomes adding the log of $2$, and tripling becomes adding the log of $3$ (side note: this means that this is a nim game, as adding until you reach some number is equivalent to starting at that number and subtracting until you get to zero).  So then the game becomes:
Start with $z=0$. Each turn, players add $\log_22=1$ or $\log_23$ to $z$. The game ends when $z > \log_2m$.
Clearly, this game will end the fastest if each players increases $z$ by $\log_23$ each turn, in which case it will (with rounding) end after $\frac{\log_2m}{\log_23 }= \log_3m = \log_2\log_3n$ turns. The longest it can take is $\log_2\log_2n$. It's not clear that "average" is well defined, but it regardless of how it's defined, it will be between these two numbers. And if we're dealing with Big-O notation, the bases of the logarithms don't matter, so we're left with $\log\log n$
A: $x$ is replaced with $x^2$ or $x^3$.
That is, $\log x$ is replaced with $2\log x$ or $3\log x$.
That is, $\log \log x$ is replaced with $\log 2+\log\log x$ or $\log 3+\log\log x$. So for $\log\log x$, we have a simple addition of random vars. In particular, the stopping time is between $\approx\frac{\log\log n-\log\log 2}{\log3}$ and $\approx\frac{\log\log n-\log\log 2}{\log2}$.
A: Notwithstanding the slightly broken English and all, the problem may be reformulated without players:

Start with $2$ and square or cube it arbitrarily. Show that the number of operations to exceed $n$ is $O(\log\log n)$.

We can take two logs, since $\log$ is strictly increasing, and get the following:

Start with $\log\log2$ and add $\log2$ or $\log3$ arbitrarily. Show that the number of operations to exceed $\log\log n$ is $O(\log\log n)$.

This is trivially true, since $\log2$ and $\log3$ are constants that are not accounted for explicitly in $O$.
