HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Asymptotic growth rate of $f(n)$ and $f(n+1)$

Submitted by: @import:stackexchange-cs··
0
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))$

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.