# What is the complexity of computing \$C(n + m, m)\$?

According to Pascal identity,(suppose $$kleq n$$)

$$binom{n}{k}=binom{n-1}{k-1}+binom{n-1}{k}$$
That give us a recurrence relation to find value $$binom{n}{k}$$.

Unfortunately, above recurrence to find value $$binom{n}{k}$$ ,without memoization ( or dynamic programming methods),needs time complexity
$$Thetaleft(2^{n}right).$$ on the other hand, with dynamic programming,
the running time is
$$Omega(n).$$

So you can’t compute $$binom{n}{k}$$ in $$min(n,k)$$ time. Because $$binom{n}{k}$$ have $$logbinom{n}{k}$$ bits,so you need at least write or read $$Omega(n)$$ bits.
{"ft_lang_label":"__label__en","ft_lang_prob":0.616713,"math_prob":0.99998116,"size":556,"snap":"2021-31-2021-39","text_gpt3_token_len":172,"char_repetition_ratio":0.1594203,"word_repetition_ratio":0.0,"special_character_ratio":0.2967626,"punctuation_ratio":0.116071425,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":1.000001,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-07-29T14:44:13Z\",\"WARC-Record-ID\":\"<urn:uuid:900cdb0d-1d87-48d6-a398-e253d02114b9>\",\"Content-Length\":\"26125\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:9fc45bf1-266e-4917-9247-d5f8e148b4e4>\",\"WARC-Concurrent-To\":\"<urn:uuid:554950ec-50da-4d6d-9d21-e3449139e3be>\",\"WARC-IP-Address\":\"173.212.203.156\",\"WARC-Target-URI\":\"https://proxies-free.com/what-is-the-complexity-of-computing-cn-m-m/\",\"WARC-Payload-Digest\":\"sha1:DRRP7KCMNXPZK6CH7KEJL65JWYOGH2KY\",\"WARC-Block-Digest\":\"sha1:PSLDGBDX4XDOERM7SE4IL36TYZCB5JHF\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-31/CC-MAIN-2021-31_segments_1627046153860.57_warc_CC-MAIN-20210729140649-20210729170649-00143.warc.gz\"}"}