Example: Suppose $H:${$1,...,n$} $\rightarrow ${$1,..,n$} be a uniform hash function. for input $x$, $z$ is equal to number of trailing zero in the right side of $H(x)$. for $0 \leq c \leq 1$ what is the order of probability $ z \geq c \log_2 n$? $C$ is constant here.
Answer: $O(1/n^c)$
How this this is can be achieved?
Update:
The Logarithm base is $2$ not $10$.
Since the hash function is uniform, to find $P(z \geq c \log n)$ we can simply count the number of elements in $S = \{1,\ldots,n\}$ that satisfy $z \geq c \log n$.
Take $n=2^p$ for some $p\in\mathbb{N}$. Then $n/2$ elements in $S$ end on one zero, $n/4$ elements end on two zeros, etc. So, $P(z \geq c \log n) = (n/2)/n = 1/2$ for $c\log n =1$, $1/4$ for $c\log n=2$, $1/8$ for $c\log n=3$, etc.
So $P(Z \geq c \log n) = (1/2)^{c \log n} = (1/2^{\log n})^c = (1/n)^c$.