関数$ f $が存在します。

Question

データ構造コースの宿題の割り当てにおいて、次の質問に遭遇しました：

"関数 $ f $ は次のようなものです。 $ f（nk）\ ne \ theta（f（f（f（f）n））一定の $ k \ geq1 $ ？ "

そのような関数がないと思いません $ f $ が存在しませんが、それを証明する方法がわからない（または1つ存在する場合はカウンターを与える）。

Answer 1

例は $ f（n）= 2 ^ {2 ^ n} $ です。さて、 $ f（n-1）= 2 ^ {2 ^ {n-1}} $ 、 $\ frac {f（n-1）} {f（n）}=frac {1} {2 ^ {2 ^ n - 2 ^ {n-1}}}=frac {1} {2 ^ {2^ {n-1}}} $ 。したがって、 $ f（n-1）\ nではなく\ theta（f（n））$ 。この例では、 $ k= 1 $ 。

Answer 2

ConterExample： $ f（n）= n！$ として $ f（n）$ です。 $ n $ $ f（n-1）$ よりも大きい時間、 $ f（n-1）\ neq \ theta（f（n））$ 。