expected number of sets generated by greedy set cover ?
Given that a cover exists, greedy will return a cover of expected size $O(p^{-1}\log n)$.
As long as $k$ is not too large, with high probability every cover has size $\Omega(p^{-1}\log n)$ 


This implies that (for $k$ not too large) greedy gives an $O(1)$-approximation with probability $1-\delta$, for any constant $\delta&gt;0$.

Here is the upper bound, followed by the lower bound.  

Upper bound

Conditioning on the event that there exists a set cover,
the greedy set-cover algorithm returns a set cover with expected size
$O(p^{-1}\log n)$.

Proof of upper bound.
Condition on the event that a set cover exists.

Assume without loss of generality that $k\ge (12/p)\ln(n)$
(otherwise, since greedy chooses at most $k$ sets, we are done).

We prove that there is a fractional set cover $X$ of expected size at most
$$\frac{2}{p} + n\exp(-pk/12).$$
By the assumption on $k$ this is $$O(1/p).$$

The upper bound will follow, because
(as is well-known) greedy returns a cover of size $O(\log n)$ 
times the size of any fractional set cover (and so, here, $O(p^{-1}\log n)$)
(see here or Chvatal).

Define the fractional cover $X$ in two stages.


Give each set $s$ weight $X_s = 2/pk$.
For each element $e$ such that $\sum_{e\in s} X_s &lt; 1$,
choose any set $s$ containing $e$ and raise $X_s$ enough to fully cover $e$.


This clearly gives a fractional set cover.  (Step 2 is well defined,
because we are conditioning on the event that there is a set cover,
that is, that each element is in some set.)

To finish we bound the expected total weight of $X$, that is, $\sum_s X_s$.

Stage 1 contributes exactly $k 2/pk = 2/p$ to the total weight.

Stage 2 contributes, in expectation, at most $n\exp(-pk/12)$,
because each of the $n$ elements has probability at most
$\exp(-pk/12)$ of being covered with weight less than 1
by stage 1. 

(To verify this, fix any element.
The element is left insufficiently covered 
iff it is contained in fewer than $kp/2$ sets.
The expected number of sets covering the element
is $kp$, so by a standard Chernoff bound the 
probability that the number falls below $kp/2$
is at most $$\exp(-(1/2)^2 k p/3) = \exp(-kp/12).$$
This ignores the conditioning, but the conditioning
only decreases the chance that the element is contained
in fewer than $kp/2$ sets.)
QED

As an aside, note that if $k$ is large enough, then greedy will almost certainly return a cover of constant size.  (E.g. if $k$ is $2n2^n$ and $p=1/2$, then won't all possible subsets be present with high probability? And in that case greedy will return just one set of course.)

Lower bound

Assuming  $p\le 1/2$, $k\le \exp(n^{1-\epsilon})$ for some $\epsilon\in [0,1/2]$,
and $s = \min((\epsilon/4p)\ln n, n^{\epsilon/2})$,
then the probability that there exists a set cover of size $s$ or less is $o(1)$.

Of course this implies that greedy does not return a set cover of size less than $s$.

The proof is probabilistic, using direct calculation and the naive union bound.
Hopefully there are no mistakes in the calculations.

Proof.
Fix $p$, $k$, $s$, $\epsilon$ as above.

The number of ways of choosing $s$ sets from the $k$ sets available 
is ${k\choose s}$.

For any fixed collection of $s$ sets, the chance that it covers all
$n$ elements is $(1-(1-p)^s)^n$.

Combining these two observations, the expected number of size-$s$ covers among the $k$ sets is
$${k\choose s} (1-(1-p)^s)^n 
~\le~ k^s \exp(-n(1-p)^s) 
~\le~ \exp\big(s\ln(k) - n e^{-2sp}\big).$$

To complete the proof, one shows that the right-hand side above is $o(1)$
(under the assumptions on $k$ and $s$).

To do that, it suffices to show that 


$n e^{-2sp} \rightarrow \infty$, and
$s\ln k \le (1/e) n e^{-2sp}$.


The first of these follows from the assumption on $s$.
The second reduces (taking logarithms) to
$$1+2ps + \ln s \le \ln(n) - \ln\ln k.$$
By the assumption on $k$ this reduces to
$$(1+2ps) + \ln s \le \epsilon \ln n.$$
This holds because the assumptions on $s$ imply that each of the two summands
on the left is at most $(\epsilon/2)\ln n$.
QED