MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 2 added 9 characters in body

First of all the $k(G)$ cannot be smaller than the size of any proper subgroup of $G$, because if $H$ is a proper subgroup, $gH$ is a coset, $g\not\in H$, then $gHgH$ does not contain intersect $gH$ (it will not contain if $g$). ghgh'=gh''$, then $g\in H$). For example, if $G$ is Abelian, $|G|$ is not prime (i.e. $G$ is not cyclic of prime order), then $k(G)>\sqrt{|G|}$: look at the size of a maximal proper subgroup.

show/hide this revision's text 1

First of all the $k(G)$ cannot be smaller than the size of any proper subgroup of $G$, because if $H$ is a proper subgroup, $gH$ is a coset, $g\not\in H$, then $gHgH$ does not contain $gH$ (it will not contain $g$). For example, if $G$ is Abelian, $|G|$ is not prime (i.e. $G$ is not cyclic of prime order), then $k(G)>\sqrt{|G|}$: look at the size of a maximal proper subgroup.