$ F $의 함수는 다음과 같습니다 : $ f (n-k) \ Ne \ theta (f (n)) $ k \ geq1 $의 경우 $?

Question

데이터 구조물에서 숙제 할당에 다음 질문을 겪었습니다. 코스 :

"함수 $ f $ 이 존재합니다 : $ f (nk) \ nk \ theta (f (n)) $ 일부 상수 $ k \ geq1 $

$ f $ 이 존재하지 않지만, 그것을 증명하는 방법을 모르겠지만 (또는 존재하는 경우 카운터 예제를 제공합니다).

Answer 1

예는 $ f (n)= 2 ^ {2 ^ n} $ 입니다.이제 $ f (n-1)= 2 ^ {2 ^ {n-1}} $ {2 ^ {n-1}} $ $\ frac {f (n-1)} {f (n)}=frac {2} {2 ^ {2 ^ n - 2 ^ {n-1}}}=frac {1} {2 ^ {2^ {n-1}}} $ .따라서 $ f (n-1) \ \ in \ theta (f (n)) $ .이 예에서 $ k= 1 $

Answer 2

반대 샘플 : $ f (n)= n! $ $ f (n) $ 은 $ N $ 시간이 $ F (n-1) $ 보다 훨씬 큽니다. $ f (n-1) \ neq \ theta (f (n)) $ .