performance of new wallet address

I study bitcoin and don't exactly understand that how new wallet generate? The documentation write below sentence: "For generate new wallet, first search that there is no such wallet" How we can found that the new wallet didn't generate before? What is complexity of search?

• Documentation for what wallet service or software? Do you have a link to said documentation? – Pieter Wuille Oct 16 '18 at 1:13
• The bitcoin.org documentation – R. Jalaei Salahi Oct 16 '18 at 1:14
• Please update your question with an actual link. – Pieter Wuille Oct 16 '18 at 1:18
• The phrase you quoted exists only in your question - it is not a quotation from any documentation indexed by Google. – RedGrittyBrick Oct 16 '18 at 10:58

I study bitcoin and don't exactly understand that how new wallet generate?

I think you mean address, not wallet. A wallet is a software application that manages your addresses, and let's you view/spend the Bitcoin associated with them.

A Bitcoin Address is a shortened form of Bitcoin script that locks the funds associated to it. In order to spend the funds, you must provide the necessary input to the script so that it equates to true when the script is executed by nodes on the Bitcoin network. This usually includes a signature of the transaction by the private key associated to the address. Here's an example of a Pay-to-Public-Key Hash (P2PKH) address:

P2PKH
16JrGhLx5bcBSA34kew9V6Mufa4aXhFe9X

Steps to generate the address:

1. Generate a random 32 byte private key. For example (do not use this): a966eb6058f8ec9f47074a2faadd3dab42e2c60ed05bc34d39d6c0e1d32b8bdf
2. Calculate it's corresponding public key using secp256k1 elliptic curve 023cba1f4d12d1ce0bced725373769b2262c6daa97be6a0588cfec8ce1a5f0bd09
3. Calculate the hash = RIPEMD160(SHA256(public-key)): 3a38d44d6a0c8d0bb84e0232cc632b7e48c72e0e
4. Encode Base58Check(hash): 16JrGhLx5bcBSA34kew9V6Mufa4aXhFe9X

See How to Generate a Bitcoin Address

How we can found that the new wallet didn't generate before? What is complexity of search?

You want to make sure you don't use a private key that someone else might have. There is no way to search all the addresses that might be known because only addresses that have received coins are on the blockchain. Also, many addresses can be derived from the same key pair using different scripts, so you can't be sure you don't have a duplicate just by checking the address.

Since a private key can be nearly any 32 byte number, there are on the order of 10^70 possibilities. You will never have a collision with another key as long as you choose a sufficiently random source for key generation. This is the most important thing to remember. For example, don't use a Brainwallet or any other low entropy source to generate a private key because it makes it easier for someone to guess.