83  名前：普通のやる夫さん[sage] 投稿日：2020/10/15(Thu) 20:41:29 ID:e9a8066e
>>78

f(n)＝2^n
g(n)＝n^100

この2つを比べたとき
「f(n)がg(n)を追い抜いてそれ以後はg(n)が追いつくことはない」という地点がありますよね？
こそういう地点がある場合に「f(n)がg(n)を支配している」って言うんですけど

「再帰的定義のみで作られた関数全てを支配している関数」ってのがあるんですよ
ビジービーバー関数と言いましてね？
ttps://ja.wikipedia.org/wiki/%E3%83%93%E3%82%B8%E3%83%BC%E3%83%93%E3%83%BC%E3%83%90%E3%83%BC