patternMinor
Asymptotic growth rate of $f(n)$ and $f(n+1)$
Viewed 0 times
andrateasymptoticgrowth
Problem
Let $f : \mathbb{R} \rightarrow \mathbb{R}$ be a continuous positive function, where $f(n)$ is integer for each integer $n$. Prove or disprove whether the following always holds:
$\qquad f(n+1) = \Theta(f(n))$
$\qquad f(n+1) = \Theta(f(n))$
Solution
Imagine any continuous, monotonically non-decreasing function $f$ such that $f(n) = n!$ for all non-negative integers $n$. Then $f(n+1) = (n+1)! = (n+1)n! = (n+1)f(n)$. Since there is no constant $c$ such that $n+1<c$, it follows that it is not true that $f(n+1) = \Theta(f(n))$. QED.
Context
StackExchange Computer Science Q#3231, answer score: 6
Revisions (0)
No revisions yet.