# Average Case runtime for random choice search

Assuming we have an array with $n$ Elements and want to find an unique element by randomly (uniformly) choosing. What would be the average case runtime?

My thoughts so far:

The chance to find the element is $\frac{1}{n}$ in every step. Thus, to find the element after $k$ steps is $(\frac{1}{n})^k$. Now we can calculate the expected value and get $\frac{n}{(n-1)^2}$. But: that doesn't really make as it returns results $< 1$ for $n > 2$.

The probability you find the element in each guess is $1/n$. The number of guesses until you find it is a geometric random variable with success probability $1/n$, whose expectation is $n$.
Your formula is wrong – the probability to find the element after $k$ steps is $(1-1/n)^{k-1} (1/n)$.
{"ft_lang_label":"__label__en","ft_lang_prob":0.90644705,"math_prob":0.9998024,"size":439,"snap":"2019-51-2020-05","text_gpt3_token_len":124,"char_repetition_ratio":0.12873563,"word_repetition_ratio":0.0,"special_character_ratio":0.29840547,"punctuation_ratio":0.097826086,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999449,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-01-18T02:03:23Z\",\"WARC-Record-ID\":\"<urn:uuid:6a5aa582-6e65-4a24-94b3-1e1eebffff2a>\",\"Content-Length\":\"134476\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:d58c718a-8724-4eb8-9a93-b07120a7bff5>\",\"WARC-Concurrent-To\":\"<urn:uuid:739b69f0-b02e-475d-baed-703940dcc112>\",\"WARC-IP-Address\":\"151.101.1.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/32566/average-case-runtime-for-random-choice-search\",\"WARC-Payload-Digest\":\"sha1:CYXAK5YF5EN22B25LC4RUED4TGJYR6NW\",\"WARC-Block-Digest\":\"sha1:3MHYZ2UZ7XYF4CIX6IDZ2TIGUJXL3EWP\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-05/CC-MAIN-2020-05_segments_1579250591431.4_warc_CC-MAIN-20200117234621-20200118022621-00086.warc.gz\"}"}