In Bluetooth network environment, device discovery is achieved by the master running the Inquiry protocol and slaves running the Inquiry Scan protocol. The master and a slave establish a connection using the Page and Page Scan protocols, respectively. Once a connection is established between a master and a slave, upper level data can be exchanged between the two devices. Thus, device discovery and connection establishment are fundamental to communication between two Bluetooth devices. While a device is in the process of discovering other devices, there is a random delay. We analyze the discovery time for different situations. We further show the delay-distribution for varied number of devices. We explain reasons of occasional long discovery time, and propose means to improve it.