Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [asymptotics]

For questions involving asymptotic analysis, including function growth, Big-$O$, Big-$\Omega$ and Big-$\Theta$ notations.

Questions involving asymptotic analysis, including function growth, Big-$O$, Big-$\Omega$ and Big-$\Theta$ notations.

  • $f(x) = O(g(x))$ as $x \to \infty$ is used to mean that for sufficiently large values of $x$, we have $|f(x)| \leq A g(x)$ for some constant $A$.

  • $f(x)=\Omega(g(x))$ is equivalent to saying that $g(x)=O(f(x))$.

  • $f(x)=\Theta(g(x))$ is used to mean that $f(x)=O(g(x))$ and that $f(x)=\Omega(g(x))$.

9469 questions
3
votes
2 answers

Getting asymptotic behaviour of an integral?

I am interested in the $\rho\sim0$ asymptotics of the following expression $$ \int_{1.1}^{\infty}\frac{\sin(k\rho)}{k^{1.9}\rho}\frac{1}{\log\frac{1}{k}}\,dk $$ any ideas of how to tackle this?
PhoenixPerson
  • 717
3
votes
0 answers

How to explore the asymptotic of an iteration

Definition Given that $f:\Bbb R\to\Bbb R$ is a real-valued function. The iteration of $f$, say $f^n$, is defined here: $f^0(x)=x$ $f^n(x)=f\left(f^{n-1}(x)\right)$ for any positive integer $n$. For example, $f(x)=x+c\implies f^{n}(x)=x+nc$, and…
Yai0Phah
  • 9,733
3
votes
1 answer

How to find asymptotic of function s=s(n): s^s = n

How to find asymptotic of function s=s(n): $s^s = n$. Please help me to solve this problem.
noname_0
  • 31
3
votes
1 answer

Asymptotic analysis Big O Big Omega

When we have $F(n) = \Omega(H(n))$ and $G(n)=\mathcal{O}(H(n))$. Can we prove that $G(n)/F(n) = \mathcal{O}(1)$? I tired to use the definitions of $\mathcal{O}$ and $\Omega$ but all I ended up with were two inequalities that I couldn't use. Thanks
ammoun
  • 155
3
votes
2 answers

Asymptotic analysis of a recurring sequence

Let $(u_n)$ be a sequence defined by: $$\begin{equation} \left\{ u_0 \geq 0 \\ \forall n \in \mathbb{N}^*, u_n = \sqrt{n+u_{n-1}} \right. \end{equation}$$ I'd like to prove that when $n \rightarrow +\infty$ : $$u_n \sim \sqrt n$$ This would…
Cydonia7
  • 891
3
votes
2 answers

If $f(n)=O(g(n))$, when is $2^{f(n)}=O(2^{g(n)})$?

There are questions that ask if $2^{f(n)}=O(2^{g(n)})$ is true (Big-O: If $f(n)=O(g(n))$, prove $2^{f(n)}=O(2^{(g(n)})$) and it clearly isn't for all $f$ and $g$. But I haven't found a question which discusses when the two can be equal. Is it true…
Picasso
  • 441
3
votes
1 answer

Two asymptotics problems

Problem 1. Estimate $\displaystyle \sum_{i=1}^n \frac{\ln i}{\sqrt{i}}$ with an absolute error $O(1)$. Problem 2. Estimate: $$\left|\left\{ \langle a,b,c \rangle\in \mathbb{N}_+^3 : abc\le n \right\}\right|$$ where $\mathbb{N}_+=\mathbb{N}\setminus…
ray
  • 1,507
3
votes
3 answers

Can two function be Big-O of each other?

Given two functions $f(n)$ and $g(n)$, is it possible that $f(n) = O(g)$ and that $g(n) = O(f)$? If the answer is yes, I have a follow-up: if $f(n)$ and $g(n)$ are Big-O of each other, does that also mean that they are Big-Omega of each other?…
UnworthyToast
  • 259
3
votes
0 answers

Is there a common name for $O(x^{cx})$ type functions?

Is there a common name for the growth rate of functions that are asymptotically on the order of $x^{cx}$, for some $c$? The term super-exponential is much too general. The factorial function grows in this way -- so would it be appropriate to say…
Dave Futer
  • 51
3
votes
3 answers

Show that $(x+1+O(x^{-1}))^x = ex^x + O(x^{x-1})$ for $x\rightarrow \infty$

So I'm trying to show that for $x\rightarrow \infty$: $$(x+1+O(x^{-1}))^x = ex^x + O(x^{x-1})$$ So these complicated big-Oh expressions are clearly going to be a recurring theme in my book, and I simply have no idea how to manipulate them in a…
Set
  • 7,600
3
votes
2 answers

Help Proving that $\frac{(1+\frac{1}{t})^t}{e} = 1 -\frac{1}{2t} + O(\frac{1}{t^2})$ for $t\geq 1$

I'm trying to prove the asymptotic statement that for $t\geq 1$: $$\frac{(1+\frac{1}{t})^t}{e} = 1 -\frac{1}{2t} + O(\frac{1}{t^2})$$ I know that $(1+\frac{1}{t})^t$ converges to $e$ and the right side looks like the first bit a of the series…
Set
  • 7,600
3
votes
1 answer

What can we say about the set of asymptotic equivalence classes of sequences?

Say that $$A := \{f : \mathbb{N} \to \mathbb{R}\}/\sim$$ where $f \sim g$ if $f$ and $g$ are asymptotically equivalent. That is, let $A$ be the set of asymptotic equivalence classes of real functions. What can be said about $A$? For…
Daniel McLaury
  • 24,656
3
votes
1 answer

Big Theta with Negative Coefficient Problem

I had a question in regards to solving a Big-Theta problem. Our professor wanted us to prove that $n^3 - 47n^2 + 18 = \Theta(n^3)$ and to do so rigorously, meaning he does not want us to use the below method: $\lim\limits_{n \to \infty}…
AlmondMan
  • 45
3
votes
0 answers

An asymptotic expansion

The function $w(x)$ satisfies $$\frac{d^2w}{dx^2} + 2x\frac{dw}{dx} - 2\beta w = 0$$ with $$w(\infty)=0 \text{ and } 0<\beta < 1.$$ By writing $w(x)= exp(-x^2)f(x)$, obtain the first two terms of an asymptotic expansion for $w(x)$ as $x \to \infty…
smith
  • 143
3
votes
1 answer

Big-O: If $f(n)=O(g(n))$, prove $2^{f(n)}=O(2^{(g(n)})$

Suppose that both f(n) and g(n) are non-negative functions. If $f(n)=O(g(n))$, is $2^{f(n)}=O(2^{(g(n)})$ true too? If not, give counter examples. I am unsure of how to proceed. What I have in mind at the moment is that since f(n) and g(n) are…
bow_one
  • 83
1 2 3
…
74 75