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?

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$
