Availability of abundant spectrum has enabled millimeter wave (mm-wave) as a prominent candidate solution for the next generation cellular networks. Highly directional transmissions are essential for exploitation of mm-wave bands to compensate high propagation loss and attenuation. The directional transmission, nevertheless, necessitates a specific design for mm-wave initial cell discovery, as conventional omni-directional broadcast signaling may fail in delivering the cell discovery information. To address this issue, this paper provides an analytical framework for mm-wave beamformed cell discovery based on an information theoretical approach. Design options are compared considering four fundamental and representative broadcast signaling schemes to evaluate discovery latency and signaling overhead. The schemes are then simulated under realistic system parameters. Analytical and simulation results reveals four key findings: (i) For cell discovery without knowledge of beacon timing, analog/hybrid beamforming performs as well as digital beamforming in terms of cell discovery latency; (ii) Single beam exhaustive scan optimize the latency, however leads to overhead penalty; (iii) Multi-beam simultaneous scan can significantly reduce the overhead, and provide the flexibility to achieve trade-off between the latency and the overhead; (iv) The latency and the overhead are relatively insensitive to extreme low block error rates.