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
0
votes
0 answers

Show that $1^k + 2^k + ... + n^k$ is $\cal O(n^{k+1})$ , using an integral.

Let k be a positive integer. Show that $f(i) = 1^k+2^k+...+n^k$ is $O(n^{k+1})$. Hi, I know that $f(i) ≤ \int\limits_{1}^{n+1}x^{k}dx$ When I integrate f(i) using this rule, I get $\frac{((n+1)^{k+1}-1)}{(k+1)}$ How do I use this information to…
big papi
  • 1
0
votes
2 answers

Can we say that Omega(O(f(n))) = O(Omega(f(n)))?

Can we say that the following condition is true? Why? $$ \Omega(O(f(n))) = O(\Omega(f(n))) $$
fhm
  • 135
0
votes
0 answers

asymptotic notation on the exponent vs asymptotic notation of an exponential

Suppose we have $O(2^{t(n)})$ and $2^{O(t(n))}$. I see that they are different. For instance: $O(2^{t(n)})^2 = O(2^{2t(n)})\neq O(2^{t(n)})$, while $(2^{O(t(n))})^2 = 2^{2O(t(n))}= 2^{O(t(n))}$. I wonder, what is the relation between them? I see…
7iat
  • 55
0
votes
0 answers

Help Big-O proof troubles

I need to prove the rule that if $f(n) \in g(n) + O(h(n))$ then $g(n)\in f(n) + O(h(n))$ I have made several attempts but never get far as I'm not quite sure where to begin.
S. Sav
  • 1
0
votes
1 answer

Disproving asymptotic relation

I'm trying to disprove that $\forall f: N\rightarrow R^+,\forall g: N\rightarrow R^+, f \in \Omega(g) \iff \lfloor f\rfloor \in \Omega(\lfloor g\rfloor).$ However I need some hints.
oksana
0
votes
1 answer

Asymptotic Expansion of integral with logarithm

I want to show that as $\epsilon \to 0$ : $$ \int_0 ^1 \frac{\ln(x)}{x+\epsilon}= -\frac{1}{2} \ln ^2 \left( \frac{1}{\epsilon} \right) -\frac{\pi^2}{6} + \epsilon \left( 1-\frac{\epsilon}{4} + \frac{\epsilon^2}{9} - \frac{\epsilon^3}{16} + ...…
multivariableExpert1
  • 39
0
votes
2 answers

How do you prove that the product of 2 functions is still big O of "h"

This is in my homework and I'm not sure how to do it: $f \circ g \in O(h^2) \implies f \in O(h) \text{ and } g \in O(h)$. I get it intuitively but writing it down in proof-form is evading me.
Feinmann
  • 1
0
votes
1 answer

Question about oblique asymptotes

I'm looking for a way of finding an oblique asymptote of (on infinity): \begin{equation} \sqrt{1 + x^2 + \sqrt{(1 + x^2)^2 - 2 x^2 \cos^2{\theta}}} \end{equation} I know that the asymptote is $\sqrt{2}x$. I'm trying to find it simply by finding…
m0nhawk
  • 1,779
0
votes
1 answer

Naive question about asymptotics

Suppose I want to investigate the behaviour of say $\sin(\delta\ln(1+\epsilon))$ for variables $\delta$ and $\epsilon.$ I want to see what orders of $\delta$ and $\epsilon$ the term comes out as. I thought I can expand $\ln$ by Taylor expansion. How…
soup
  • 1,414
0
votes
1 answer

Bounds and asymptotic equivalence

Let us suppose 3 functions $f$, $g$ and $h$ where $$f < g \leq h$$ and $$\lim_{x \to \infty} f(x)/h(x) = 1.$$ Can we conclude that $\lim_{x \to \infty} f(x)/g(x) = 1$ and $\lim_{x \to \infty} g(x)/h(x) = 1$? Thank you.
Dingo13
  • 435
0
votes
1 answer

Operations on asymptotic equivalents

The asymptotic equivalence is denoted by $\sim$ and we say that $f \sim g$ if $\lim_{x \to \infty} f(x)/g(x) = 1$ I have read that powers in $\mathbb{N}^*$ preserve the asymptotic equivalences. Do real powers preserve equivalence? 1) Let us suppose…
Dingo13
  • 435
0
votes
0 answers

Asymptotic expansion of $e^{-x}$ as $x \rightarrow \infty$

I want to find the asymptotic expansion of $e^{-x}$ as $x \rightarrow \infty$. I know that $\psi_n(x) = x^{-n}$ is an asymptotic sequence, and so I want my expansion to be in the form $\sum_{n=0}^{\infty} \frac{a_k}{x^k}$. I have no idea how to go…
user112495
  • 384
  • 4
  • 13
0
votes
1 answer

Show $ (\ln\ln(x) )(\ln x )+\ln\ln\ln x=o_{+\infty} (\ln x )^{2}+\ln\ln\ln\ln x $

I would like to show that $$ (\ln\ln(x) )(\ln x )+\ln\ln\ln x=o_{+\infty} (\ln x )^{2}+\ln\ln\ln\ln x $$ by using these methods : limit $$\lim_{x\to +\infty }\dfrac{ (\ln\ln(x) )(\ln x )+\ln\ln\ln x }{ (\ln x )^{2}+\ln\ln\ln\ln x…
Educ
  • 4,780
0
votes
0 answers

how is this theorem called?

let be the sum $$ f(\epsilon) = \sum_{n=1}^{\infty}e^{-n\epsilon} $$ $ f(0)= \infty $ diverges for any positive epsilon $ \epsilon >0 $ the sum converges assume we know the value of $ f(\epsilon) $ as $ \epsilon \to 0 $ then the asymptotics of the…
Jose Garcia
  • 8,506
0
votes
1 answer

$\int_1^x (1+\frac{1}{t})^t \, dt = ex - \frac{e}{2}\log(x) + O(1)$

I want to show this, but I'm not really sure where to get started. Integrating by parts hasn't really gotten me anywhere useful, and I'm not really sure what else to try.
user112495
  • 384
  • 4
  • 13
1 2 3
…
74 75