Birthday Attack Probability of Collision in Introduction to Modern Cryptography I have some questions about the chapter of Birthday Attack in Introduction to Modern Cryptography.


  When $q=\Theta(2^{l/2})$ the probability of this collision is roughly $1/2$


What's the meaning of $\Theta(.)$ and $\Theta(2^{l/2})$, and why the probability of this collision is roughly 1/2 when the $q=\Theta(2^{l/2})$

Thanks in advance.
We say $f(n)=\theta(g(n))$ if 
$$
cg(n)\leq f(n)\leq Cf(n),\quad 0&lt;c\leq C&lt;\infty
$$
as $n\rightarrow \infty.$ 

Apply the $\ell-$bit hash function to $k$ randomly chosen inputs. Let $n=2^{\ell}.$ 

The chance of two values picked being unique is $n- 1 \over n$ because when picking the second value you only have $n-1$ unique values left in the range. Repeating this argument, 
the chance of picking $t$ unique values is:

$${n - 1 \over n} \times {n- 2 \over n} \times \cdots \times {n- (k- 1) \over n}.$$

This is exactly the same as the limit for the birthday paradox.

Now $1-x \leq e^{-x}$ and hence 
$1-(v/n) \leq e^{-v/n}$ for $1\leq v\leq n,$ and thus the probability of no collisions is at most
$$e^{-{1 \over n}} \times e^{-{2 \over n}} \times \cdots \times e^{-{k - 1 \over n}} =\exp\left\{-{1 + 2 + \cdots + (k-1) \over n}\right\}$$
which equals 
$$e^{-{k(k-1)/2 \over t}} = e^{-{k(k-1) \over 2n}} $$

The chance of a collision is 1 minus this quantity. Plugging in $k=\sqrt{n}=\sqrt{2^{\ell}}$ yields a value not too far from $1/2.$