Tagged Questions
4
votes
1answer
43 views
Iterated function?
$$f(n) = \frac{n}{\lg n}$$
$$g(n) = \min (i \ge 0: f^i(n)\le 2)$$
In other words, $g(n)$ is the number of times $f(n)$ needs to be iterated to reduce $n$ to 2 or less.
What's a tight bound on ...
1
vote
1answer
19 views
How do we determine as to how long we should sum an asymptotic series of a function to get the answer correct up to a particular precision?
As an example, consider the asymptotic expansion for polygamma function . What should be the min value of 'k' in the equation to get the answer correct upto a particular precision, say pth. Is there ...
2
votes
0answers
35 views
Upper bound for linear function
What may be more surprising is that when $a>0$, any linear function $an +b$ is $\mathcal{O}(n^2)$ which is easily verified by taking $c = a + |b|$ and $n_o = \max (\frac{-b}{a}, 1)$.
$$an + b ...
0
votes
0answers
24 views
I don't understand how the sign of argument works in a function with arguments that could be positive, negative or in between
this formula is from http://en.wikipedia.org/wiki/Airy_function
i want to know what is the value of Ai(large negative number) but if z is negative the formula below gives minusxminus = positive ...
1
vote
2answers
32 views
The growth rate of the functions with respect to each other
There are two functions , for example $f(n)=3\sqrt{n}$, and $g(n)=\log n$. Which one dominates, in other words, is $f(n)=O(g(n))$ or $f(n)= \Omega(g(n))$?
Thank you.
0
votes
1answer
78 views
What does it mean when you say that the function is bounded?
What I figured is that it means that the function has an upper bound, however I came across this text:
Here since g(x) either equal or less to f(x), |g(x) / f(x)| must be bounded right? Since the ...
0
votes
1answer
43 views
asymptotic expansion, interpretation
I am interested in asymptotic behavior of a function at infinity:
$$
f(r)=\frac{0.04962 e^{-2 r} (r-1.000)}{\left(\left(e^{-2 r}\right)^{2/3}+0.06119\right)^2 r}
$$
Tried ...
3
votes
2answers
24 views
Simple question about asymptotics of a ratio
What is the largest exponent $\alpha$ such that the ratio between $ n^{\alpha}$ and $ (\sqrt{n} / \log{ \sqrt n}) $ still remains asymptotically bounded (can assume $n$ positive integer) ?
2
votes
1answer
89 views
Are there straightforward methods to tell which function has fastest asymptotic growth without a calculator?
For example, suppose I wanted to determine which of the following has the fastest asymptotic growth:
$n^2\log(n)+(\log(n))^2$
$n^2+\log(2^n)+1$
$(n+1)^3+(n-1)^3$
$(n+\log(n))^22^{100}$
Are there ...
2
votes
2answers
49 views
Study of a series of functions
I've to study this series:
$$\sum_{n=1}^\infty e^{\sqrt n\,x}$$
My teacher wrote that with the asymptotic comparison with this series:
$$\sum_{n=1}^\infty\frac{1}{n^2}$$
My series converges ...
0
votes
1answer
104 views
On determining if a function is eventually non-decreasing
I've just had an idea or intuition, but I couldn't be sure if it is correct or not:
Let's say I have a function $f(n)$ such that it can be expressed as $\frac{g(n)}{h(n)}$ where $g(n)$ and $h(n)$ are ...
1
vote
1answer
107 views
little o notation with natural logs
I'm having trouble with little o notation.
Help me show that:
$2(n^2 + 100n)\log^5n = o(n^2\sqrt{n})$.
It is the last hwk on my sheet and I don't understand it, if someone can help me with ...
2
votes
1answer
79 views
big O notation with asymptotically nonnegative increasing functions
Let $f(n)$ and $g(n)$ be asymptotically nonnegative increasing functions. Show:
$f(n) · g(n) = O((\max\{f(n), g(n)\})^2)$, using the definition of big-oh.
I can't quite figure this out, can ...
3
votes
1answer
154 views
All asymptotes of $f(x)=\sqrt{x^2-4x}+\frac{1}{x^2-1}$
Find the number of all possible asymptotes of: $$f(x)=\sqrt{x^2-4x}+\frac{1}{x^2-1}$$
Since we know $\sqrt{ax^2+bx+c}\approxeq \sqrt{a}\big|x+\frac{b}{2a}\big|$ when $(x\rightarrow\pm\infty)$ so, ...
0
votes
1answer
187 views
Asymptotic notation - some equations.
i have a problem with proof one of this facts:
$2^{2^n}$ = $\Theta (n^n)$ or
$2^{2^n}$ = $O (n^n)$ or
$2^{2^n}$ = $\Omega (n^n)$
and to proof one of this:
$(n^n)$ = $\Theta (2^{2^n})$
$(n^n)$ = ...
2
votes
3answers
204 views
Intermediate growth rates
Is there any simple function/formula $f(n)$, which eventually dominates every $cn$ for every $c$, and is eventually dominated by $a \cdot n \cdot \ln^k(n)$ for every $a,k \in \mathbb{Z}$, where ...
0
votes
1answer
434 views
Compare growth rate of functions
I was given homework to sort some (14) functions in order of their growth rate. I am confused about two functions $3^\sqrt{\log n}$ and $n^{\log n}$: about where these two lie within those 14 ...
0
votes
2answers
94 views
Finding $\Omega(f(n))$
Is there a standard way to find a $\Omega$ of a function $f(n)$ ?
I mean, I'm trying to understand how to determine:
$$g(n)=\Omega(f(n))$$
where $f(n)$ is a polynomial or logarithmic function
I ...
4
votes
3answers
3k views
Family of functions with two horizontal asymptotes
I'm looking for the equation of a family of functions that roughly resembles the sketch below (with apologies for the crudeness of said sketch):
Properties I'm looking for:
...
